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.

  • $\begingroup$ $p=101, y^2=x^3+10x+1$ seems to be a counterexample to your suspicion. $\endgroup$ Oct 19, 2017 at 8:24

2 Answers 2


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.