I am looking at a elliptic curves of the form $E:y^2=x^3+x$, i.e. short Weierstrass curves wtih $a=1$ and $b=0$, defined over a field $\mathbb{F}_p$ with $p$ being a safe prime. Somewhat interestingly, this is kind of an inverse Koblitz curve (where $a=0$ and $b\ne0$).

Because $b=0$, the case of $x=0$ will always be a valid point of order 2 at $(0, 0)$.

  1. As far as I can tell, such a curve has a necessary cofactor $h=2\cdot2$, but I can't seem to find the reason for another point of order 2.
  2. Are there other things that can be said about the curve's order?

The reason this is of interest is because older Windows product key systems used curves of this particular form.


2 Answers 2


The curve $E$ given by the equation $y^2 = x^3 + x$ is a Montgomery curve. Those are are the form $By^2 = x^3 + Ax^2 + x$, so in this particular case we have $A=0$ and $B=1$.

The points of order $2$ have their $x$-coordinate as a root of $x^3 + x$. If $-1$ is a square over $\mathbf F_p$, then the points of order $2$ are $(0,0)$, $(\sqrt{-1},0)$ and $(-\sqrt{-1},0)$. Otherwise there is only $(0,0)$.

On those curves, the closest to a prime for the cardinality is $4\cdot\text{prime}$ for both the curve and its quadratic twist (such as the Goldilock curve), or $8\cdot\text{prime}$ and $4\cdot\text{prime}$ (such as Curve25519).


Claim: If $p>5$ is a safe prime, then $\#E(\mathbb F_p)=p+1$.

Proof: Since $p$ is a safe prime, we have $p\equiv3\pmod4$. The curve $y^2 = x^3 + x$ over $\mathbb C$ has complex multiplication by $\mathbb Z[\mathrm i]$, given by the automorphism $(x,y) \mapsto (-x, \sqrt{-1}\cdot y)$. As every $p\equiv3\pmod4$ is inert in $\mathbb Z[\mathrm i]$, the reduction modulo $p$ is supersingular. By definition, this means $p\mid t$, where $t:=p+1-\#E(\mathbb F_p)$. Due to the Hasse bound $\lvert t\rvert \leq 2\sqrt p$, the only possibility is $t=0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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