In the last article, we established that computing Q = d · G is a one-way operation — fast going forward, impossible in reverse. But fast how, exactly?
d is a 256-bit number. It can be as large as 2²⁵⁶. If Bitcoin computed Q = d · G by adding G to itself d times, one step at a time, it would take longer than the age of the universe. Every transaction would be impossible to process.
So how does it actually compute in practice?
GCD — Greatest Common Divisor
Before getting into the mechanics, it helps to understand one small concept first: the greatest common divisor.
The GCD of two numbers is the largest number that divides both numbers. Since the natural number 1 divides any other integer, 1 is always a common divisor of any two non-zero integers, but it is not necessarily the greatest. Take 12 and 8 as an example:
GCD(12, 8) = 4
4 is the largest number that divides both without a remainder. But if two numbers share no common factors at all, like 14 and 9, their GCD is 1. When that's the case, they are called coprime. Two integers are coprime if and only if their greatest common divisor is 1. That property — two numbers being coprime — is what makes the next section possible.
Fermat's Little Theorem
Previously, we mentioned that division inside a finite field works through something called Fermat's Little Theorem. Here is what that actually means.
In a finite field of prime order p, dividing by a number a is not done the way you would normally divide. Instead, Bitcoin computes:
a⁻¹ = a^(p−2) mod p
This gives the modular inverse of a — the number that, when multiplied by a, gives 1 inside the field. It replaces division entirely, and keeps the result bounded within the finite field.
But there is a condition. This only works when a and p share no common factors — when GCD(a, p) = 1. In other words, when they are coprime.
This is exactly why Bitcoin's finite field has a prime order. A prime number shares no common factors with any integer smaller than itself. Every element in the field is automatically coprime with p, which means Fermat's Little Theorem holds for every element, division always works, and the field never breaks.
Take a small example. In a field of order 7, finding the inverse of 3:
3^(7−2) mod 7 = 3⁵ mod 7 = 243 mod 7 = 5
Check: 3 · 5 = 15 → 15 mod 7 = 1 ✅
That is division inside a finite field. No stepping outside the set.
Double-and-Add
d can be as large as 2²⁵⁶. Adding G to itself that many times one step at a time is not just slow — it is impossible. A different approach is needed.
That approach is double-and-add.
The idea is to decompose d into its binary representation and work through it from left, doubling and adding.
Here's how it works:
say d = 9. In binary: 9 = 1001
- You always work from left to right.
- You always ignore the first digit.
- 0 = double
- 1 = double and add
1 -> Ignore first digit
0 -> Double gives us 2
0 -> Double to give 4
1 -> Double gives 8, add makes it 9
if d = 13. In binary: 13 = 1101
1 -> Ignore first digit
1 -> Double and add gives us 3
0 -> Double to give 6
1 -> Double gives 12, add makes it 13
GCD tells you when two numbers are coprime. Fermat's Little Theorem uses that property to make division possible inside a finite field without ever stepping outside it. And double-and-add makes point multiplication on a 256-bit curve fast enough to run.
Together, they are what make elliptic curve cryptography practically usable. The math is hard to reverse and fast to compute — and that gap between the two directions is the entire foundation Bitcoin's security sits on.
