How does point addition work on an elliptic curve, and what is the "double-and-add" algorithm?
To add points P and Q: draw a line through them, find where it intersects the curve at a third point R, then reflect R over the x-axis. This is the group operation. "Double-and-add" is the ECC equivalent of square-and-multiply.
* The line through P and Q hits the curve at a third point R′; reflecting R′ over the x-axis gives R = P + Q. Adding coordinates directly would land off the curve. *
Point addition (P + Q where P ≠ Q):
- Draw a line through P and Q
- The line intersects the curve at a third point $R'$
- Reflect $R'$ over the x-axis → $R = P + Q$
Point doubling (P + P = 2P):
- Draw the tangent line to the curve at P
- The tangent intersects the curve at $R'$
- Reflect → $R = 2P$
Special cases:
- $P + \mathcal{O} = P$ (point at infinity is the identity)
- $P + (-P) = \mathcal{O}$ (a point plus its reflection = infinity)
Double-and-add (analogous to square-and-multiply):
- To compute $k \cdot P$ (scalar multiplication): express $k$ in binary, scan left to right
- For each "0" bit: double the accumulator
- For each "1" bit: double then add P
- This computes $k \cdot P$ in $O(\log k)$ operations instead of $O(k)$
Tip: In ECC, "addition" replaces "multiplication" and "scalar multiplication" ($k \cdot P$) replaces "exponentiation" ($g^k$). The notation changes but the structure is identical to DH/ElGamal.
Go deeper:
Corbellini — ECC part 2: finite fields and discrete logarithms — point addition over $\mathbb{F}_p$ and scalar multiplication, with runnable code.- Elliptic curve point multiplication — Wikipedia — the add/double formulas and the double-and-add algorithm.