How do I generate group table for elliptic curves over finite fields Can someone please explain how to generate a group table for an elliptic curve over a finite field? The number of solutions or points are about 16 and it is not possible to do them by adding each individually. Complete novice about elliptic curves, some help would be appreciated thank you.


For instance how would i go about solving this $y^2\equiv x^3 +2\pmod {7}$ over a finite field? It has 9 points.


 A: Another approach (see Example $15.5$ at Elliptic Curve Cryptography), is the following.
Take $x = 0 \ldots 6$ and for each $x$ solve: $$y^2 \equiv x^3 + 2 \pmod {7}$$
You can set-up two tables (note: each $y$ can produce zero, one or two points):


*

*$x = 0 \implies y^2 = 2 \pmod 7$

*$x = 1 \implies y^2 = 3 \pmod 7$

*$x = 2 \implies y^2 = 3 \pmod 7$

*$x = 3 \implies y^2 = 1 \pmod 7$

*$x = 4 \implies y^2 = 3 \pmod 7$

*$x = 5 \implies y^2 = 1 \pmod 7$

*$x = 6 \implies y^2 = 1 \pmod 7$


We also calculate for $y = 0 \ldots 6$:


*

*$y = 0 \implies y^2 = 0 \pmod 7$

*$y = 1 \implies y^2 = 1 \pmod 7$

*$y = 2 \implies y^2 = 4 \pmod 7$

*$y = 3 \implies y^2 = 2 \pmod 7$

*$y = 4 \implies y^2 = 2 \pmod 7$

*$y = 5 \implies y^2 = 4 \pmod 7$

*$y = 6 \implies y^2 = 1 \pmod 7$


This yields (just match the two tables up) the following sets of points:


*

*$x = 0, y = 3, 4$

*$x = 1, y = -$

*$x = 2, y = -$

*$x = 3, y = 1, 6$

*$x = 4, y = -$

*$x = 5, y = 1, 6$

*$x = 6, y = 1, 6$


This gives us eight points and we add the point at infinity, $I = (\infty, \infty)$, for a total of nine points.
You can use Hasse's Theorem to quickly bound the number of points over $\mathbb{F}_{q}$, where $q = 7$ in your example and is given by:
$$q + 1 - 2 \sqrt{q} \le \#E(\mathbb{F}_q) \le q + 1 + 2 \sqrt{q}$$
You can also look into Point Counting Algorithms to determine the actual number of points on the curve.
It is worth mentioning that you can get free computer algebra tools like SAGE, (there is now a cloud based online variant), GP/Pari and others.
Lastly, you should compare the solution above with what @Travis wrote up.
A: For any group with $9$ elements, one can simply pick a nonidentity element $g$ and compute the subgroup it generates. Note that there are only two groups of this order $\mathbb{Z}_9$ and $\mathbb{Z}_3 \times \mathbb{Z}_3$, and that the former has exactly $2$ elements of order $3$.
If $g$ has order $9$, your group is isomoprhic to $\mathbb{Z}_9$, with generator $g$, which gives you the table immediately, as we can write any sum as
$(ag) + (bg) = (a + b)g$, $a, b \in \mathbb{Z}_9$.
If $g$ has order $3$, then pick an element $h$ not in the subgroup $\{0, g, 2g\}$. If $h$ has order $9$, proceed as above. If $h$element has order $3$, then the group has at least three elements of order $3$ (namely, $g$, $2g$, $h$), so the group is isomorphic to $\mathbb{Z}_3 \times \mathbb{Z}_3$, and can be identified with $\langle g \rangle \times \langle h \rangle$, which again gives a complete multiplication table: $(ag, bh) + (cg, dh) = ((a + c)g, (b + d)h)$, $a, b, c, d \in \mathbb{Z}_3$.
