Let $p$ be a prime such that is $p=a^2+b^2$, where $a$ is odd, $b$ is even and $p \equiv 1 \pmod{4}$.
I have an integer $n = p + 1 + 2a$ or $n = p + 1 - 2a$, either of these may be given and chosen arbitrarily for convenience.
- Is there an efficient way of factoring $n$?
- Is there an efficient way of checking any integer $m$ in a certain range of integers $m_{min} < m < m_{max}$ divides $n$ evenly?
Context: This may be a case of an XY problem. I am asking this because I am interested in quickly finding elliptic curves of the form $E: y^2 = x^3 - kx$ over a prime field $\mathbb{F}_p$ with a cofactor $m$ being in a certain range. This is not used for cryptography. From theorem 4.23 on p. 115 of Lawrence C. Washington's Elliptic Curves: Number Theory and Cryptography, 2nd ed., we know that $\#E(\mathbb{F}_p) = p + 1 - 2a$ if $k$ is a biquadratic residue modulo $p$ and $\#E(\mathbb{F}_p) = p + 1 + 2a$ if $k$ is a square residue but not a biquadratic residue. Finding curves is therefore quick and efficient, but I fail to see any way to factorize it efficiently to find an $m$ in the pre-defined range $m_{min} < m < m_{max}$.
Partial Answer
Describes factoring $n$ when $a, b$ are in special form.
$$n=p+1±2a=a^2+b^2+1±2a$$
Let $b=2c^2$. Note that $b$ is even.
$$n=a^2±2a+1+4c^4$$ $$=(a±1)^2+4c^4$$ If $a±1=d^2$, $d$ even, $n$ can be written as $$n=d^4+4c^4$$ Now $n$ has the Aurifeuillian factorization $$n=d^4+4c^4=(d^2-2cd+2c^2)(d^2+2cd+2c^2)$$
Note that if $d$ is even, $a$ is odd and $p \equiv 1 \mod 4$.