The group structure of elliptic curve over $\mathbb F_p$

I want to find the group of the elliptic curve $y^2=x^3-x$ over $\mathbb F_p$ for all primes $p \le 29$. But I know only 1 fact about the structure of this group: $E(\mathbb F_p)=\mathbb Z/m \mathbb Z \times \mathbb Z/nm\mathbb Z$ for $\gcd (m,p)=1, p =1 \mod m$. It doesn't really help. Is there any method to find the group without huge calculation?

• Define "huge" :-) In general the Schoof-Elkies-Atkin algorithm is the best (I think), but that is surely overkill for these small groups. – Jyrki Lahtonen Apr 6 '14 at 12:57
• @Jyrki Lahtonen As I understood this algorithm just find the number of points on an elliptic curve. I'd like to find the structure of that group. I hope there is a trick to find it without calculation in these cases:) – user130893 Apr 6 '14 at 13:08
• IIRC you can then also find the group structure with some tricks involving the Weil pairing. Anyway, the orders of these small groups are easy to calculate anyway. You do need to use the point addition/doubling formulas to make any headway. – Jyrki Lahtonen Apr 6 '14 at 13:16
• What is q in the question? – Álvaro Lozano-Robledo Apr 6 '14 at 13:58
• sorry, misclick, $q=p$. – user130893 Apr 6 '14 at 14:00

The elliptic curve $E:y^2=x^3-x$ has discriminant $\Delta=64$, so it only has bad reduction at $p=2$. For any other $p>2$, the curve has good reduction and $E/\mathbb{F}_p$ is an elliptic curve, in particular, $E(\mathbb{F}_p)$ is a finite abelian group.

Take for instance $p=5$. You can easily find all the points of $E$ in $\mathbb{P}^2(\mathbb{F}_5)$, and verify that there are $8$ points (counting the point at infinity). Since $E(\mathbb{F}_5)$ is finite abelian of order $8$, it must be isomorphic to $(\mathbb{Z}/2\mathbb{Z})^3$, $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/4\mathbb{Z}$, or $\mathbb{Z}/8\mathbb{Z}$. The first possibility is not really possible, because the $q$ torsion of an elliptic curve (for any prime $q$) is formed by the direct sum of, at most, two cyclic groups of order $q$ (i.e., $E[q]\subseteq \mathbb{Z}/q\mathbb{Z}\times \mathbb{Z}/q\mathbb{Z}$). Now it is a matter of identifying $E(\mathbb{F}_5)$ as $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/4\mathbb{Z}$, or $\mathbb{Z}/8\mathbb{Z}$, and you can prove that in fact $E(\mathbb{F}_5)\cong \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/4\mathbb{Z}$, by finding $3$ distinct points of exact order $2$ (if the group was $\mathbb{Z}/8\mathbb{Z}$ there would be only one point of exact order $2$).

Similarly, when $p=11$, you can count $E(\mathbb{F}_{11})$ and see that there are $12$ points (don't forget about the point at infinity!). Now the possible isomorphism classes are $\mathbb{Z}/12\mathbb{Z}$, or $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/6\mathbb{Z}$, and you can prove that $E(\mathbb{F}_{11})\cong \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/6\mathbb{Z}$ by finding $3$ distinct points of order $2$.

Note that the point at infinity, together with the points $(-1,0),(0,0),(1,0)$ form a subgroup of $E(\Bbb Q)$ isomorphic to $(\Bbb Z/2\Bbb Z)^2$, you will find this subgroup in $E(\Bbb F_p)$ for any $p > 2$.

Moreover, your curve has complex multiplication (by $i : (x,y) \mapsto (-x,iy)$), so a lot can be said via the explicit class field theory for $\Bbb Q(i)$.

If $p \equiv 3 \pmod 4$, the number of points on $E(\Bbb F_p)$ is $p+1$. Since there is no prime factor in common between $p+1$ and $p-1$ except possibly $2$, and we know that $\Bbb (\Bbb Z/2\Bbb Z)^2$ is a subgroup, but not $(\Bbb Z/4\Bbb Z)^2$ (because $p-1 \equiv 2 \pmod 4$), we must have $E(\Bbb F_p) \approx (\Bbb Z/2\Bbb Z) \times (\Bbb Z/\frac{p+1}2\Bbb Z)$.

The points $(i,1-i),(i,-1+i),(-i,1+i),(-i,-1-i)$ with the previous four form a subgroup of order $8$ in $E(\Bbb Q(i))$ (isomorphic to $(\Bbb Z/2\Bbb Z) \times (\Bbb Z/4\Bbb Z)$), so this subgroup will always be present in $E(\Bbb F_p)$ with $p \equiv 1 \pmod 4$

If $p \equiv 1 \pmod 4$, then there is a unique way to write $p = (a+ib)(a-ib)$ with $a+ib \equiv 1 \pmod {2+2i}$. Then, $\# E(\Bbb F_p) = p+1-2a$, and $E(\Bbb F_p)$ contains a factor $(\Bbb Z/m\Bbb Z)^2$ if and only if $(a,b) \equiv (1,0) \pmod m$ (the Frobenius automorphism $Frob_p$ acts on $E(\overline{\Bbb F_p})$ a lot like multiplication by $a+ib$ does on the torus $\Bbb Q[i] / \Bbb Z[i]$).

For variety, we can compute $E(\mathbf{F}_3)$ by using Hasse's theorem, which says it has between $4 - 2\sqrt{3}$ and $4 + 2\sqrt{3}$ points: so it's somewhere from $1$ to $7$ points.

Because the curve has three points of order $2$, $\mathbf{Z}/2\mathbf{Z} \times \mathbf{Z}/2\mathbf{Z}$ must be a subgroup. And thus it must be the entire group, since the only possible group order divisible by $4$ is $4$ itself.