Walk through the double-and-add algorithm step by step: compute $13 \cdot P$ on an elliptic curve.
Convert 13 to binary: $(1101)_2$. Start with P, then for each remaining bit left-to-right: always DOUBLE, and additionally ADD P for each "1" bit. Trace: $P \to 3P \to 6P \to 13P$ (the bits after the leading 1 are 1, 0, 1 → double-add, double, double-add).
* Scanning the bits of 13 = (1101)₂ after the leading 1: double for every bit, plus an extra add for each 1 — three doublings and two adds reach $13P$. *
$13 = (1101)_2$ — process bits left to right, skip the leading 1:
| Step | Bit | Operation | Accumulator | Value |
|---|---|---|---|---|
| Start | 1 | Initialize | $P$ | $1 \cdot P$ |
| 1 | 1 | Double, then Add | $2P + P$ | $3P$ |
| 2 | 0 | Double only | $2 \cdot 3P$ | $6P$ |
| 3 | 1 | Double, then Add | $2 \cdot 6P + P$ | $13P$ |
Verification: $1 \to 3 \to 6 \to 13$. The exponent sequence matches!
How to read the binary representation:
- $13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0 = (1101)_2$
- Leading "1": initialize accumulator to $P$
- Second bit "1": double ($2P$), add ($3P$)
- Third bit "0": double only ($6P$)
- Fourth bit "1": double ($12P$), add ($13P$)
Another example: $25 = (11001)_2$:
| Step | Bit | Operation | Value |
|---|---|---|---|
| Start | 1 | Init | $P$ |
| 1 | 1 | D+A | $3P$ |
| 2 | 0 | D | $6P$ |
| 3 | 0 | D | $12P$ |
| 4 | 1 | D+A | $25P$ |
Effort: For a $k$-bit number: exactly $k-1$ doublings + (number of "1" bits - 1) additions.
- For 256-bit ECC key: ~255 doublings + ~127 additions ≈ 382 operations
- Without double-and-add: 256 individual additions — impossibly slow for real key sizes
Tip: This is identical to Square-and-Multiply (SAM) for RSA, just with "double" replacing "square" and "add" replacing "multiply." The binary scanning technique is exactly the same.
Go deeper:
Elliptic curve point multiplication — Wikipedia — the double-and-add algorithm and its variants.- Exponentiation by squaring — Wikipedia — the multiplicative twin (square-and-multiply) it mirrors.