2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ No and can't use it either. It has to be done manually $\endgroup$ – Paradox 101 Jan 22 '15 at 7:40
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Your example curve is given by $\mathcal E: y^2 = x^3 + 2$.

First, find all of the points on the curve over the finite field $\mathbb F_7$. Working modulo 7 we have $$\begin{array}{|c|ccccccc|} \hline x,y & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline y^2 & 0 & 1 & 4 & 2 & 2 & 4 & 1 \\ \hline x^3+2 & 2 & 3 & 3 & 1 & 3 & 1 & 1 \\ \hline \end{array}$$

We want all pairs of points $[x,y]$ for which $y^2 \equiv x^3+2 \pmod 7$. The table gives us $$\mathcal E/\mathbb F_7 =\{\mathcal{O}, [0, 3], [0, 4], [3, 1], [3, 6], [5, 1], [5, 6], [6, 1], [6, 6]\}$$

There are standard formulae for combining any two points. See this section of Wikipedia.

You can save yourself some time by noting that if the line through any two points $P$ and $Q$ is vertical then $P + Q=\mathcal{O}$. For example $(0,3) + (0,4) = \mathcal{O}$. Moreover, since the group operation is commutative (i.e. $P + Q = Q + P$), we get $(0,4) + (0,3) = \mathcal{O}$ for free. Similarly for $(3,1) + (3,6)$, $(5,1) + (5,6)$ and $(6,1) + (6,6)$. Obviously $\mathcal O + P = P = P + \mathcal O$ for all $P$.

This gives us $25$ out of the $81$ entries in the group table without having to apply a single formula. Of the remaining $56$ entries, you need only compute $32$ explicitly, because if you know $P+Q$ you also know $Q+P$. In reality, you don't even need to find all of these $32$ since if you have one space in any row/column then you can complete that row/column since every row/column must contain each element once, and only once; you only need find $24$ explicitly, i.e. $30\%$ of the entries.

Applying the formulae from Wikipedia gives me the group table $$\begin{array}{|c|ccccccccc|} \hline & \mathcal{O} & [0, 3] & [0, 4] & [3, 1] & [3, 6] & [5, 1] & [5, 6] & [6, 1] & [6, 6] \\ \hline \mathcal O & \mathcal{O} & [0, 3] & [0, 4] & [3, 1] & [3, 6] & [5, 1] & [5, 6] & [6, 1] & [6, 6] \\ [0,3] & [0,3] & [0,4] & \mathcal O & [6,1] & [5,6] & [3,1] & [6,6] & [5,1] & [3,6] & \\ [0,4] & [0, 4] & \mathcal O & [0, 3] & [5, 1] & [6, 6] & [6, 1] & [3, 6] & [3, 1] & [5, 6] \\ [3,1] & [3, 1] & [6, 1] & [5, 1] & [3, 6] & \mathcal O & [6, 6] & [0, 3] & [5, 6] & [0, 4] \\ [3,6] & [3, 6] & [5, 6] & [6, 6] & \mathcal O & [3, 1] & [0, 4] & [6, 1] & [0, 3] & [5, 1] \\ [5,1] & [5, 1] & [3, 1] & [6, 1] & [6, 6] & [0, 4] & [5, 6] & \mathcal O & [3, 6] & [0, 3] \\ [5,6] & [5, 6] & [6, 6] & [3, 6] & [0, 3] & [6, 1] & \mathcal O & [5, 1] & [0, 4] & [3, 1] \\ [6,1] & [6, 1] & [5, 1] & [3, 1] & [5, 6] & [0, 3] & [3, 6] & [0, 4] & [6, 6] & \mathcal O \\ [6,6] & [6, 6] & [3, 6] & [5, 6] & [0, 4] & [5, 1] & [0, 3] & [3, 1] & \mathcal O & [6, 1] \\ \hline \end{array}$$

Notice that all of the elements of the group $\mathcal E/\mathbb F_7$ have order three. There are only two finite groups of order nine. Since no element of the group $\mathcal E/\mathbb F_7$ has order nine, it cannot be cyclic. Hence $$\mathcal E/\mathbb F_7 \cong \mathbb Z/3\mathbb Z \oplus \mathbb Z/3\mathbb Z$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm sorry I still don't get it. I need to generate a group table for two groups of order 3 which is isomorphic to group of order 9. I know the points for order 9 but i have to find them for two groups of order 3 and then generate a table accordingly $\endgroup$ – Paradox 101 Jan 22 '15 at 2:42
  • $\begingroup$ It's not entirely clear to me what you mean. Do you mean, you know that your group is isomorphic to $\mathbb{Z}_3 \times \mathbb{Z}_3$? $\endgroup$ – Travis Jan 22 '15 at 3:01
  • $\begingroup$ Yes it was mentioned by the instructor. $\endgroup$ – Paradox 101 Jan 22 '15 at 3:02
  • $\begingroup$ Great, so pick out one generator of each factor, and then write down the table. $\endgroup$ – Travis Jan 22 '15 at 3:05
  • $\begingroup$ So I have to consider both the groups separately and generate the points separately according to the curve? And then consolidate the answers? $\endgroup$ – Paradox 101 Jan 22 '15 at 3:13

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.