Need this for probabilistic [factoring algorithm](https://mathoverflow.net/questions/283767/conjecturally-unsafe-rsa-primes-p-27a227a7).


Let $p$ be sufficiently large prime and $E$ the elliptic curve
$E /\mathbb{F}\_p: y^2=x^3+ax+b$. Let $o=\#E(\mathbb{F}\_p)$.
$\psi\_n$ denote the $n$-the division polynomial of $E$.


If $X$ is the $x$ coordinate on $E$ we have $\psi\_o(X)=0$.


What hypothesis on $E$ do we need to make it only if?


$$\psi\_o(X)=0 \iff X^3+aX+b=\square$$


I suspect it is enough $E$ to not be supersingular.


Would prefer reference rather than proof.



When the $o$-th division polynomial of an elliptic curve over finite vanishes only at $x$ coordinates?
If $x$ in $\mathbb{F}\_p$ is such that $\psi\_o(x)=0$ but $x^3+ax+b$ is not a square in $\mathbb{F}\_p$, let $y$ be the square root of $x^3+ax+b$ in $\mathbb{F}\_{p^2}$ and $P=(x,y)$. Then $P$ has order $d$ dividing $o$. There is also a rational point on $E$ of order $d$, so $Fr^2-1 =0$ in $E[d]$, where $Fr$ is Frobenius, because $Fr(P)=-P$. So $x^2-tx+p \equiv x^2 -1 \pmod{d}$, where $o=p+1-t$. Hence $t \equiv 0, p+1 \equiv 0 \pmod{d}$, so $d$ is a common factor of $p+1$ and $o$. So if the gcd of $o,p+1$ is $1$, there is no such $x$.


