Bitcoin part 4: Number Theory

First, the bad news: This will be the longest and most mathematical installment in the series. The good news: You can skip it entirely and not miss anything, because this is almost entirely unrelated to Bitcoin. But I feel like writing about it.

This is a detour from the detour. I want to walk through a concrete example to show why you might believe that trapdoor one-way functions actually exist. This is not the specific class of such functions used by Bitcoin, but it is simple enough (I hope) to cover in a blog post.

Definition: Two integers are congruent modulo n if they leave the same remainder when divided by n. For example, 13 is congruent to 37 modulo 12, because they both leave a remainder of 1 when divided by 12 (13 = 12*1 + 1 while 37 = 12*3 + 1).

Notation: We write this as $13\equiv37\pmod{12}$. Note the triple-equals sign, pronounced “is congruent to”.

Also note that 13 ≡ 37 ≡ 1 (mod 12), because 1 = 12*0 + 1.

Imagine, for a moment, that you lived in a world where everything happened modulo 12. In this world, we would call 12 “the modulus”. You can do both addition and multiplication in this world. For example, 7*5 ≡ 35 ≡ 11 (mod 12). You can also substitute congruent numbers for one another any time you like. For example, since 7 ≡ 19 and 5 ≡ 17, we also have 19*17 ≡ 11 (mod 12). We could also see this by multiplying 19*17 = 323, then taking the remainder when dividing by 12, obtaining the same answer: 11. It is pretty easy to show this always works.

Since we can substitute congruent numbers for each other, and there are only 12 possible remainders when dividing by 12, we can go further than saying “1 and 13 are congruent”; we can simply say “1 and 13 are different ways to represent the same thing”. Put another way, in the “modulo 12” world there are effectively only 12 numbers, and you can represent them any way you like. A mathematician might represent them as “0, 1, 2, … , 11”. A grandfather clock might represent them as “I”, “II”, “III”, …, “XII”. No matter how you represent them, a set of such objects plus the rules for “multiplying” and “adding” them fully defines a mathematical structure. (As an aside, the structure in this example is called “the ring of integers modulo 12”. The structure underlying Bitcoin’s trapdoor one-way functions is called an “elliptic curve over a finite field”.)

Bear with me.

Now, 12 is a good example if you are thinking about a clock, but starting with a prime number for the modulus is more interesting. So let’s shift our view to look at the world modulo 11, and let’s think about the function f(x) = x2 in this world. Obviously, this function is easy to compute; for example, 5² ≡ 25 ≡ 3 (mod 11). What about inverting this function; i.e. extracting square roots? Is that easy?

It is not so obvious how to start from, say, the number 3, and find a number whose square leaves a remainder of 3 when divided by 11. (Other than guessing numbers, squaring them, and checking their remainders, of course.) Yet it is possible: You simply raise it to the power $\frac{11+1}{4}$; that is, you cube it. 3³ ≡ 27 ≡ 5 (mod 11). And as we just saw, 5² ≡ 3, so 5 is the square root of 3 (mod 11).

Or rather, 5 is a square root of 3. There is another, namely -5, also known as 6 (mod 11).

So, to find a square root of any number (mod 11), you just cube the number. This always gives the right answer if the number actually has a square root. Half of them do not, so you need to double-check your answer at the end by squaring it.

This works in general, by the way, for any prime modulus that is one less than a multiple of four. To find a square root of y modulo 31, for instance, you just compute y to the power $\frac{31+1}{4}$, or y8. Again, this works as long as y actually has any square roots (mod 31). You need to double-check at the end by squaring. If the double-check fails, then y is not a perfect square modulo 31. (This is all true, but it is not obvious unless maybe your name is “Fermat”.)

Number theory is just brimming with such beautiful non-obvious facts.

If your prime modulus is one more than a multiple of four, extracting square roots is more complicated but still feasible.

So, bottom line: Extracting square roots modulo a prime is easy. Even using large primes with hundreds or thousands of bits, for a computer it is still easy.

Seriously now, bear with me.

Suppose p and q are primes, and n = p*q. Is it easy to extract square roots modulo n?

As it turns out, that is a very interesting question.

Answer: Yes, assuming you actually know p and q.

Read John Cook’s page for the gory details, but the basic idea is that there is a tight relationship between the world modulo n and the pair of worlds modulo p and modulo q. (This tight relationship is called the “Chinese Remainder Theorem”.)

What if someone wants to compute square roots (mod n) knowing n but not its factors p and q? Well, in that case, they are out of luck, because the problem is “hard” in the cryptographic sense, as far as anyone knows.

By knowing p and q, you can do things modulo n that other people cannot do. And that includes extracting square roots. But why should you believe it is so hard? Just because I say so?

No. Suppose someone had a “clever technique” for extracting square roots modulo n without knowing the factors of n. Then they could do something very interesting. Step 1: Pick a random number x. Step 2: Square x to get x² (mod n). Step 3: Use the “clever technique” to extract a square root y. Step 4: If x≡y or x≡-y (mod n), loop back to Step 1; else print out x and y and stop.

Every time they do this loop, there is a 50% chance that Step 4 will print two numbers and stop. (Not too hard to prove, if you have internalized the Chinese Remainder Theorem…) So before very long, they will have x and y, where $x\not\equiv \pm y\pmod{n}$, and such that

x² ≡ y² (mod n)
x² – y² ≡ 0 (mod n)
(x – y)(x + y) ≡ 0 (mod n)

To say something is zero (mod n) is to say it is divisible by n. So here we have two numbers, x-y and x+y, whose product is divisible by n. By definition, n = p*q where p and q are prime. Therefore, by a very old theorem, either x-y is divisible by p or x+y is divisible by p, and similarly for q. But if x-y were divisible by both p and q, then it would be divisible by n, so we would have $x-y\equiv0\pmod{n}$, and thus $x\equiv{y}\pmod{n}$. But we specifically found x and y such that this is not the case! Similarly, if x+y were divisible by both p and q, it would be divisible by n, so we would have $x+y\equiv0\pmod{n}$ and therefore $x\equiv{-y}\pmod{n}$. Again, we specifically found x and y such that this is not the case.

In other words, p divides evenly into one of x-y and x+y, and q divides evenly into the other. Therefore the Greatest Common Divisor (GCD) of x-y and n must be either p or q. And calculating GCDs is the oldest algorithm in the world.

Conclusion: If someone could cleverly extract square roots (mod n), they could also factor n. But anybody who can factor large numbers can become very famous, and collect a bunch of prize money besides. As far as anyone knows (or is willing to publish), factoring is hard.

Thus, if you just pick big primes p and q and multiply them to get n, you can publish the function $g(x) = x^2\pmod{n}$ without revealing p or q. You have just created your own personal trapdoor one-way function (called a Rabin function), such that inverting it is provably as hard as factoring n. And since very many very smart people have tried and failed to factor big numbers quickly, it is a reasonable bet that inverting your function is hard.

Bitcoin does not use Rabin functions, but it does use things in the same number-theoretic ballpark, with similar reasons for why you might expect them to be hard to invert.

If you followed none of that, relax because it really does have nothing to do with understanding Bitcoin.