On $E: y^2 \equiv x^3 + 3x + 8 \pmod{13}$ the group has $|E| = 9$ points. Compute $9 \cdot (12, 2)$ with double-and-add, given $2 \cdot (12,2) = (1, 8)$, $2 \cdot (1,8) = (2, 3)$, $2 \cdot (2,3) = (12, 11)$. What result do you expect before computing?
Expect $\mathcal{O}$, because multiplying any point by the group order gives the point at infinity. Indeed $8P = (12, 11) = -P$, so $9P = 8P + P = \mathcal{O}$.
Step 1: write the scalar in binary. $9 = 8 + 1 = (1001)_2$.
Step 2: scan the bits left to right. The leading 1 just loads $P = (12, 2)$. For each further bit: always double, and on a 1 also add $P$.
| Bit | Operation | Result |
|---|---|---|
| 1 (leading) | start | $P = (12, 2)$ |
| 0 | double | $2P = (1, 8)$ |
| 0 | double | $4P = (2, 3)$ |
| 1 | double, then add $P$ | $8P = (12, 11)$, then $8P + P = \mathcal{O}$ |
Why the last addition gives $\mathcal{O}$: $(12, 11)$ and $(12, 2)$ have the same $x$ and $11 \equiv -2 \pmod{13}$, so they are negatives of each other ($-(x; y) = (x; -y)$). The line through them is vertical and "meets" the curve only at infinity.
Why you could predict it: by Lagrange, the order $k$ of any point divides the group order, so $|E| \cdot P = \mathcal{O}$ for every point. Here $k$ can only be 1, 3 or 9. Since $3P \neq \mathcal{O}$, $(12, 2)$ has order 9 and generates the whole group.
Exam tip: an addition table for the curve lets you read off every intermediate point instead of computing slopes by hand.