Group Structure

Overview

This section describes the group structure of elliptic curves. Hereinafter, $\mathbb{Z}_{n}$ denotes a cyclic group of order $n$.

Hankerson et al. (2006)Darrel Hankerson, Alfred J. Menezes, and Scott Vanstone. Guide to Elliptic Curve Cryptography. Springer Professional Computing. New York, 2006. Springer. give the following theorem to describe the group structure of $E\left(\mathbb{F}_{p}\right)$:

Theorem 1: group structure of an elliptic curve

Let E be an elliptic curve over a finite field $\mathbb{F}_{p}$. Then, $E\left(\mathbb{F}_{p}\right)$ is isomorphic to $\mathbb{Z}_{n_{1}} \oplus \mathbb{Z}_{n_{2}}$, where $n_{1}$ and $n_{2}$ are unique positive integers such that $n_{2} \mid n_{1}$ and $n_{2} \mid p-1$. Furthermore, they give the following statement:

It holds that $\# E\left(\mathbb{F}_{p}\right)=n_{1} n_{2}$. If $n_{2}=1$, then $E\left(\mathbb{F}_{p}\right)$ is a cyclic group. If $n_{2}>1$ is a small integer, $E\left(\mathbb{F}_{p}\right)$ is said to be almost cyclic.

Example

We consider the elliptic curve $E: y^{2}=x^{3}+1$ over $\mathbb{F}_{5}$ of Example 1 :Addition_of_points_example_1, where we’ve shown the order of each element of $E\left(\mathbb{F}_{5}\right)$. According to this corollary :Element_order , it holds that $|P|=|\langle P\rangle|$, in other words, the order of each element $P \in E\left(\mathbb{F}_{p}\right)$ is equal to the order of the cyclic subgroup generated by $P$. As each point on $E$ (except the point $\mathcal{O}$ ) has an order of $2, 3, or space 6$, the curve $E$ contains cyclic groups of these orders. For example, it’ss

$$\langle(0,1)\rangle:(0,1) \rightarrow(0,4) \rightarrow \mathcal{O}$$

or

$$\langle(2,2)\rangle:(2,2) \rightarrow(0,4) \rightarrow(4,0) \rightarrow(0,1) \rightarrow(2,3) \rightarrow \mathcal{O}.$$

This example shows that the choice of the point that generates the cyclic subgroup is of great importance. For the intractability of ECC algorithms, we usually want subgroups with high order $n$, so in the most favorable case, $\# E\left(\mathbb{F}_{p}\right)$ is prime itself because then the entire group is a cyclic group by this corollary :cyclicGrp_Corollary_3, and thus each point of (except $\mathcal{O}$ ) is a generator of order $n$.