Modern Cryptography and Elliptic Curves: Simple Examples of Elliptic Curve Group

Exercise from P.185 of Modern Cryptography and Elliptic Curves - A Beginner’s Guide.

Calculate the elliptic curve group generated by $y^2 = x^3 + 3x + 6$ over $\mathbb{F}_7$.

By substituting all possible points, it is easy to determine that $[0, 1, 0], [3, 0, 1], [6, 3, 1]$ and $[6, 4, 1]$ are the elements of the group. Since it is a group of order 4, it must be either the Klein-4 group or $\mathbb{Z}_4$. Since $[6, 3, 1]$ and $[6, 4, 1]$ are inverses of each other, this must be the cycic group of order 4, and $[6, 3, 1]$ is a generator.

As an example, $[3, 0, 1] \oplus [6, 3, 1] = [6, 4, 1]$ by following the formula in the textbook

Calculate the elliptic curve group generated by $y^2 = x^3 + 2$ over $\mathbb{F}_7$.

By looking at the square and cube of each element in $\mathbb{F}_7$, we can easily determine that

$[0, 3, 1]$
$[0, 4, 1]$
$[3, 1, 1]$
$[3, 6, 1]$
$[5, 1, 1]$
$[5, 6, 1]$
$[6, 1, 1]$
$[6, 6, 1]$
$[0, 1, 0]$

are the elements of the group. Since it’s abelian it has to be either $\mathbb{Z}_9$ or $\mathbb{Z}_3 \times \mathbb{Z}_3$. I calculated:

$[0, 3, 1]^2 = [0, 4, 1]$.
$[3, 1, 1]^2 = [3, 6, 1]$.

If the square of a non-identity element equals its inverse, its order is 3. And the inverse of an element of order 3 has order 3. Therefore, we have found at least 4 elements of order 3. Hence, it cannot be $\mathbb{Z}_9$, so it has to be $\mathbb{Z}_3 \times \mathbb{Z}_3$.

Calculate the elliptic curve group generated by $y^2 = x^3 + 4$ over $\mathbb{F}_7$.

It is easy to figure out that the elements are $[0, 2, 1]$, $[0, 5, 1]$ and $[0, 1, 0]$. There is only one group of order 3 and that is $\mathbb{Z}_3$.