How do you determine the order of a point on an elliptic curve? Walk through computing $\text{ord}(P)$ for $P(0, 3)$ on $y^2 \equiv x^3 + 3x + 2 \mod 7$ (group order 9).

Compute successive multiples $2P, 3P, 4P, ...$ until you reach $\mathcal{O}$. Since the group has order 9, possible element orders are divisors of 9: $\{1, 3, 9\}$. For $P(0,3)$: if $3P \neq \mathcal{O}$, the order must be 9.

* Adding $P$ repeatedly walks a closed cycle that only returns to $\mathcal{O}$ after 9 steps, so $\text{ord}(P)=9$ — $P$ generates the whole group. *

Step 1 — Determine possible orders:

• Group order = 9. Divisors of 9: $\{1, 3, 9\}$
• Only $\mathcal{O}$ has order 1
• So $P$ has order 3 or 9

Step 2 — Compute $2P$ using point doubling:

• $\lambda = \frac{3 \cdot 0^2 + 3}{2 \cdot 3} \mod 7 = \frac{3}{6} \mod 7 = 3 \cdot 6^{-1} \mod 7$
• $6^{-1} \mod 7 = 6$ (since $6 \cdot 6 = 36 \equiv 1 \mod 7$)
• $\lambda = 3 \cdot 6 = 18 \equiv 4 \mod 7$
• $x_3 = 16 - 0 = 16 \equiv 2 \mod 7$
• $y_3 = 4(0-2) - 3 = -11 \equiv 3 \mod 7$
• $2P = (2, 3)$

Step 3 — Compute $3P = 2P + P$:

• $\lambda = \frac{3-3}{2-0} = \frac{0}{2} = 0$
• $x_3 = 0 - 0 - 2 = -2 \equiv 5 \mod 7$
• $y_3 = 0(0-5) - 3 = -3 \equiv 4 \mod 7$
• $3P = (5, 4)$

Step 4 — Since $3P \neq \mathcal{O}$, the order is NOT 3. Therefore $\text{ord}(P) = 9$ — $P$ is a generator!

Distribution of elements in this group:

• $\varphi(1) = 1$ element of order 1 (just $\mathcal{O}$)
• $\varphi(3) = 2$ elements of order 3
• $\varphi(9) = 6$ elements of order 9 (generators)
• Total: $1 + 2 + 6 = 9$ ✓

Go deeper:

• Lagrange's theorem (group theory) — Wikipedia — why a point's order must divide the group order.
• Corbellini — ECC part 2 (order of a point) — subgroups and orders on a curve.