Need this for probabilistic factoring algorithm.
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.
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$.
Here's a slight improvement of Felipe Voloch's argument. Elements that aren't $x$ coordinates of points of $E$ are exactly the $x$ coordinates of non-$2$-torsion points of the quadratic twist $E'$ of $E$. Such elements are roots of the $n$th division polynomial if and only if they are $n$-torsion points on $E'$.
So if the only $d$ dividing the order of $E$ and the order of $E'$ is $2$, the only torsion points on $E'$ of order dividing $o$ are $2$-torsion points, whose $x$-coordinates lie in $E$.
This happens when $\gcd (o(E), o(E')) \leq 2$ which because $o(E)=p+1-a_p$, $o(E')=p+1+a_p$, and thus $o(E')=2p+2-o(E)$. happens when $\gcd ( o(E), 2p+2)) \leq 2$.
This is a slightly weaker condition than Felipe Voloch's.
In fact it's also fine if $x^3+ax+b$ has $3$ roots in $\mathbb F_p$ and $\gcd(o(E),2p+2)=4$.
