Scalar multiplication

Adding a point to itself k times is written kG. Doing it in the obvious way takes k steps; doing it in binary takes about log₂ k.

Adding a point to itself over and over is common enough to deserve a name and a notation: kG means G added to itself k times. It is called scalar multiplication, though nothing is being multiplied in the ordinary sense — k is a plain integer, G is a point, and the operation between them is the chord-and-tangent rule from the previous lesson.

Done literally, computing 13G costs twelve additions. Done in binary, it costs five. The trick is the one you would use to compute 3¹³ by hand: write the exponent in binary and square your way up, multiplying in a factor whenever the bit is set. Here, squaring becomes doubling and multiplying becomes adding.

double-and-add, left to right

13 = 1101 in binary

bit  operation      running scalar
 1   start at G     1
 1   double         2
     add G          3
 0   double         6
 1   double         12
     add G          13

5 operations instead of 12

The saving here is unremarkable. What matters is the shape of it: the naive route costs k operations, the ladder costs about log₂ k of them. For a 256-bit scalar that is the difference between 10⁷⁷ operations and roughly 380 — between impossible and instantaneous. Every public key in the world is one run of this ladder.

Now try to go backwards

Given G and kG, recover k. On this curve you can simply walk the group: add G to itself and count the steps until the target appears, at most eighteen tries. On a curve with 2²⁵⁶ points that walk never finishes. The best known general-purpose method, Pollard’s rho, cuts the work to about the square root of the group size — which for a 256-bit curve is still 2¹²⁸ steps, a number with no physical interpretation.

This asymmetry is called the elliptic-curve discrete logarithm problem, and it is the sole reason any of this is secure. Not the curve equation, not the field, not the encoding: just the fact that this particular ladder runs easily forwards and not at all backwards.

Your turn

Compute 13G, then count what it cost

G = (5, 1). Walk the double-and-add ladder for k = 13. Each rung is one point addition you already know how to do. The panel below hands you the shape of the walk — which rungs there are and what scalar each one reaches — and leaves the arithmetic to you.

13 = 1101 in binary — walk it left to right

	start at G (bit 1)	1G
…

13G =

Your turn

How many point operations did the ladder perform?

Count doublings and additions together, and do not count loading G into the accumulator — that is where the walk starts, not a step it takes. Then compare with the naive route: adding G to itself until you reach 13G costs 12 additions.

operations =

Why does this matter so much?

Saving seven operations on a toy curve is nothing. The point is how the two counts grow. The naive route costs k operations; the ladder costs about log₂ k of them:

k                        naive           ladder
13                       12              5
1000                     999             14
a typical 64-bit k       ~1.8 * 10^19    ~94
a typical 256-bit k      ~1.2 * 10^77    ~382

(one doubling per bit, one addition per set bit;
 half the bits are set on average)

A 256-bit private key is usable precisely because the forward direction fits in a few hundred operations. Going backwards — recovering k from kG — has no such shortcut, and that gap is what you are relying on every time you use HTTPS.

What you now know

kG is computed by doubling and adding along the bits of k, never by k−1 additions.
The ladder costs one doubling per bit plus one addition per set bit.
Forwards is cheap and backwards is not — that asymmetry is the whole security story.