If I toss a coin and it lands heads, I choose two primes from the heads pile and multiply them together. If it lands tails, I choose two primes from the tails pile and multiply them together. Once I’ve tossed my coin and done my calculation, I send the answer to my opponent in Tokyo. It happens to be 6,497. Since the answer will always have a remainder of 1 upon division by 4, it’s impossible for him, without knowing the primes, to tell whether the two primes I’ve chosen were from the heads pile or the tails pile. Now he is in a position to call heads or tails.
To see if he has won, I just need to send him the two primes I chose. In this case, they were 89 and 73—two primes from the heads pile. Since no other primes will multiply together to give 6,497, I have given him enough information with the number 6,497 to prove I haven’t cheated, but not enough information so that he can cheat.
Actually, that’s not strictly true. If he can crack 6,497 into 89 x 73, then he knows to call heads, but as long as I choose the primes big enough (much, much bigger than two-digit numbers), it’s almost impossible with current computing power to crack the product into its prime factors. A similar principle is used in the codes that protect credit card numbers sent across the Internet.
An Easy Challenge
I’ve tossed a coin. I’ve taken two primes from the heads pile or from the tails pile and multiplied them together. The number I get is 13,068,221. Did the coin land heads or tails? Try answering this without a computer. (The answer is at the end of the chapter.)
A Tough Challenge
What if the number is 5,759,602,149,240,247,876,857,994,004,081,295,363,338,151,725,852,938,901,132,472,828,171,992,873,665,524,051,005,072,817,707,778,665,601,229,693?
This time, you can use a computer.
WHY CRACKING NUMBERS EQUALS CRACKING CODES
Bob runs a website selling soccer shirts in England. Alice lives in Sydney and wants to buy a shirt from the website, and she wants to send her credit card details without anyone else being able to see them. Bob publishes a special code number on his website; let’s say it’s 126,619. This code number is a bit like a key that locks away Alice’s message and makes it secure. So when Alice visits the website, she gets a copy of the encoding key that Bob has published and uses it to “lock” her credit card.
What actually happens is that Alice’s computer performs a special mathematical calculation on this number, 126,619, and her credit card number. The credit card number is now encoded and can be sent publicly over the Internet to Bob’s website. (You can see the details of this calculation in the next section.)
But hold on—isn’t there a problem with this? After all, if I’m a hacker, what’s to stop me from visiting Bob’s website, getting another copy of the key, and unlocking the message? The intriguing thing about these Internet codes is that you need a different key to unlock the door, and that key is kept very securely at Bob’s headquarters.
The decoding key is the two primes that, multiplied together, give the number 126,619. What Bob actually does is choose the two primes 127 and 997 to build his encoding key, and it is these two primes that Bob has to use to undo the mathematical calculation that Alice’s computer performed to scramble her credit card number in the first place. Bob has published the encoding key 126,619 on his website, but he keeps the two decoding primes 127 and 997 very secret.
If I can work out the two primes whose product is 126,619, I can hack into the card numbers being sent to Bob’s website. Now, 126,619 is small enough for me to divide it by one number after another and find the primes 127 and 997 after not too long. You wouldn’t be able to use this method on real websites, because their keys are based on much larger numbers—so large that finding the pair of primes by trial and error is almost impossible.
So confident are the mathematicians who invented the code that for many years, they were offering a $200,000 prize to anyone who could find the two prime factors of this 617-digit number:
25,195,908,475,657,893,494,027,183,240,048,398,571,429,282,126,
204,032,027,777,137,836,043,662,020,707,595,556,264,018,525,880,
784,406,918,290,641,249,515,082,189,298,559,149,176,184,502,808,
489,120,072,844,992,687,392,807,287,776,735,971,418,347,270,261,
896,375,014,971,824,691,165,077,613,379,859,095,700,097,330,459,
748,808,428,401,797,429,100,642,458,691,817,195,118,746,121,515,
172,654,632,282,216,869,987,549,182,422,433,637,259,085,141,865,
462,043,576,798,423,387,184,774,447,920,739,934,236,584,823,824,
281,198,163,815,010,674,810,451,660,377,306,056,201,619,676,256,
133,844,143,603,833,904,414,952,634,432,190,114,657,544,454,178,
424,020,924,616,515,723,350,778,707,749,817,125,772,467,962,926,
386,356,373,289,912,154,831,438,167,899,885,040,445,364,023,527,
381,951,378,636,564,391,212,010,397,122,822,120,720,357.
If you tried to crack this 617-digit number by trying one prime at a time, you’d need to work through more numbers than there are atoms in the universe before you got to them. Not surprisingly, the prize was never claimed, and in 2007, the offer was withdrawn.
As well as being virtually uncrackable, these prime-number codes have another rather novel feature, one which solved a problem that had dogged all previous codes. Before this prime-number code was invented, conventional codes were like a lock for which the same key is used to both lock and unlock the door. These Internet codes are like a new sort of lock: one key locks the door, but a different key unlocks it. This allows a website to freely distribute keys to lock messages, while keeping very secret the other key that unlocks messages. If you’re feeling brave, here are the glorious details of how this Internet code really works. We start by introducing a curious calculator.
What Is a Clock Calculator?
The cutting-edge codes that are used on the Internet actually depend on a mathematical invention from hundreds of years before the Internet was ever dreamed of: the clock calculator. In the next section, we’ll find out how clock calculators are used in the Internet codes, but first, we’ll look at how these calculators work.
Let’s start with the 12-hour clock. Addition on such a clock is something we’re all familiar with—we know that four hours after nine o’clock will be one o’clock. This is the same as adding all the numbers together and working out the remainder after division by 12, and it is written like this:
4 + 9 = 1 (modulo 12)
We write “modulo 12” because 12 is the modulus, the point after which the numbers start again. We could do similar sums on clocks with different numbers of hours rather than just sticking to 12. For example, on a clock with ten hours:
9 + 4 = 3 (modulo 10)
How do we multiply numbers on a clock calculator? Multiplication consists of doing addition a certain number of times. For example, 4 x 9 means taking four 9s and adding them together. So where does the hand on the 12-hour clock end up after adding together four 9s? 9 + 9 is the same as six o’clock. Each time we add another 9, the hand on the clock winds back three hours until we eventually get to 12 o’clock. Since 0 is such an important number in mathematics, we actually call this zero o’clock on a clock calculator. So we get this strange-looking answer:
4 x 9 = 0 (modulo 12)
What about raising a number to some power? Let’s take 94, which means multiply 9 together four times. We’ve just learned how to do modular multiplication, so we should be able to do this easily enough. Because the numbers are getting quite big now, it will be easier here to take the remainder after division by 12 rather than trying to chase numbers around the clock. Let’s start with 9 x 9, which is 81. What’s the remainder upon division by 12—in other words, what is 81 o’clock? It turns out to be 9 again. And however many times we multiply 9 together, we always end up with 9:
9 x 9 = 9 x 9 x 9 = 9 x 9 x 9 x 9 = 94 = 9 (modulo 12)
The answer on a clock calculator is achieved by calculating the answer on a normal calculator and then taking the
remainder after division by the number of hours on the clock. But the strength of the clock calculator is that often you don’t have to calculate things on the conventional calculator first. Can you work out what 799 is on a 12-hour clock calculator? Hint: work out 7 x 7 first, then multiply the answer by 7 again. Do you see the pattern?
Fermat made a fundamental discovery about calculations on a clock calculator with a prime number of hours—say p —on it. He found that if you take a number on this calculator and raise it to the power p, you always get the number you started with. This is now called Fermat’s little theorem, to distinguish it from his famous “last” theorem.
Here are some calculations on prime and nonprime clocks:
Table 4.13
Now, 5 is prime, and if I calculate 2 to the power of 5 on a five-hour clock calculator, the answer is 2 again. So 25 = 2 (modulo 5). The magic is guaranteed to work if the number of hours on the clock is prime. It doesn’t necessarily work if you take a non-prime-number clock. For example, 6 isn’t prime, which explains why on the six-hour clock, 26 ends up not at 2 but at 4.
As the clock hand maps out the hours, a pattern emerges. After p – 1 steps, we are guaranteed at the next step to return to where we started, so the pattern repeats itself every p – 1 steps. Sometimes the pattern repeats itself several times during the p – 1 steps. On a clock with 13 hours, here’s what we see when we run through the different powers of 3 from 31, 32, and so on up to 313: 3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3.
The hand doesn’t visit all the times on the clock, but there is still this repeating pattern that brings it back to three o’clock after multiplying 3 together 13 times.
We’ve already seen similar math at work in chapter 3, in the perfect shuffles that can be used to cheat at poker. There, we varied the number of cards in the pack and asked how many perfect shuffles it would take to return the pack to its original order. A pack with 2N cards can sometimes take a full 2N – 2 shuffles, but sometimes it can take far fewer. For a pack of 52 cards, only eight perfect shuffles sees the pack return to its original order, while a pack with 54 cards needs 52 perfect shuffles.
Fermat never fully explained his working-out, and he left it as a challenge to future generations of mathematicians to explain his discovery and show why it always works for prime-number clocks. It was Leonhard Euler who eventually came up with a proof for why this magic always works on prime-number clocks.
Fermat’s Little Theorem
Here’s an explanation of Fermat’s little theorem. The theorem says that, on a clock with a prime p number of hours on it,
Ap = A (modulo p)
The proof is tough, but not technical: you’ll just need to stay focused to follow it.
Let’s start with an easy case to get us going. If A = 0, the theorem is true because however many times we multiply 0 together, we always get 0. So let’s suppose that A is not 0. We’ll set out to show that if we multiply A together p – 1 times on this clock, then we get to one o’clock. This will suffice to prove the theorem, because multiplying 1 by A again must bring us to A.
First, we make a list of all the hours on the clock, excluding 0. There are p – 1 of them: 1, 2, . . . , p – 1. Now we multiply each number in the list by A on our clock calculator and get
A × 1, A × 2, . . . , A × (p – 1) (modulo p)
The hours in this list must be just the same as those in the original list—1, 2, . . . , p – 1—but in a different order; if this were not the case, then either one of the answers is 0 or two answers are the same. There isn’t room for anything else to happen, because there are only p hours on the clock.
Suppose that A × n and A × m give the same time on the p-hour clock, where n and m lie between 1 and p – 1 (I’ll show why this means that n = m). So A × n – A × m= A x ( n – m) is 0 on the clock calculator—that is, A × ( n – m) on our ordinary calculator is divisible by p.
The key to the next step of the proof is to use the fact that p is a prime number. Like a chemical molecule, the number A × ( n – m) is built by multiplying together the prime-number atoms that make up A and the prime-number atoms that make up n – m. Now, p is prime—one of the atoms of arithmetic—and can’t be cracked any further. Because p divides into A × ( n – m) with no remainder, it must be one of the atoms used to build A × ( n – m), because there is only one way to build a number by multiplying primes. But p doesn’t divide into A with no remainder, so it must be in the list of atoms used to build n – m. In other words, n – m is divisible by p. But what does that mean? It means that n and m are the same time on our p-hour clock. You can use a similar argument to show that A × n can’t be zero o’clock if neither A nor n are zero o’clock.
Note that it is very important that the clock have a prime number of hours—we have seen already that 4 × 9 is 0 on the 12-hour clock without either 4 or 9 being 0.
Now we have two lists—1, 2, . . . , p – 1 and A × 1, A × 2, . . . , A × (p – 1)—consisting of the same numbers but in a different order. Here we can use a nice trick, one that Fermat himself had probably discovered. If we multiply all the numbers on either list together, we get the same answer, because the order in which we multiply things doesn’t matter. The first list gives us 1 × 2 × . . . × (p – 1), which we can write as (p – 1)! The second list consists of A multiplied together p – 1 times, and again 1 to p – 1 multiplied together. After a little rearrangement, this gives us (p – 1)! × Ap – 1. And these give the same answer on our clock calculator:
(p – 1)! = (p – 1)! × Ap – 1 (modulo p)
This means that (p – 1)! × (1 – Ap – 1) is divisible by p, and we use the same trick as before. None of the numbers 1, 2, . . . , p – 1 are divisible by p, so (p – 1)! can’t be divisible by p. The only possibility is that 1 – Ap – 1 is divisible by p. And this means that the calculation Ap – 1 on the clock calculator always gives the answer 1—just what Fermat had teased mathematicians to explain.
There are several interesting ingredients in this argument. It is certainly important that if A × B is divisible by a prime p, then either A or B must also be divisible by that prime—something that follows from the special property of the primes. But the beautiful moment for me comes in seeing the same thing—this list of numbers 1, 2, . . . , p – 1—in two different ways: lateral thinking at its best.
How to Use a Clock to Send Secret Messages over the Internet
We are now almost ready to show how these clocks are used to send secret messages over the Internet.
When you buy something on a website, your credit card number is encrypted by your computer using the website’s public clock calculator, so the website needs to tell your computer how many hours are on this clock. This is the first of two numbers that your computer receives. Let’s call this number N. In our example of Bob’s soccer-shirt website, this number was 126,619. There is also a second encoding number that your computer needs to do the calculation, which we’ll call E. Your credit card number C is encoded by raising it to the power E, as calculated by the clock calculator with N hours. In this way, you get the scrambled number CE (modulo N ), and that’s the number your computer sends to the website.
But how does the website unscramble this number? Fermat’s prime-number magic is the key. Let’s suppose that N is a prime-number clock. (We’ll see later that this isn’t quite good enough for a secure code, but it will help us understand where we’re going.) If we multiply the number CE together enough times, then C will magically reappear. But how many times (D ) must we multiply CE together? In other words, when does (CE )D = C on the clock with p hours?
Of course, if E x D = p, this works. But p is prime—so there can’t be any such number D. Now, if we keep multiplying C together, then there is another point in which we are guaranteed to get C appearing again as the answer. The next time the credit card number appears is when we raise it to the power 2(p – 1) + 1. It appears again when we raise it to the power 3(p – 1) + 1. So to find the decoding number, we need
to find a D such that E x D = 1 (modulo (p – 1)). This is a much easier equation to solve. The problem is that because E and p are public numbers, it’s also easy for a hacker to find the decoding number D. To make it safe, we must use a discovery made by Euler about clocks with p x q hours on them, not just p hours.
If you take a time C on a clock with p × q hours, how long does it take for C, C × C, C × C × C, . . . to repeat itself? Euler discovered that the pattern repeats itself after (p – 1) × (q – 1) steps. So to get back to the original time, you need to raise C to the power (p – 1) × (q – 1) + 1, or k × (p – 1) × (q – 1) + 1, where k is the number of times the pattern repeats itself.
So now we know that in order to decode a message C E on a clock with p × q hours, we must find a decoding number D such that E × D = 1 (modulo (p – 1) × (q – 1)), so we have to do a calculation on a secret clock calculator with (p – 1) × (q – 1) hours. A hacker knows only the numbers N and E, and if he wants to find the secret clock, he must uncover the secret primes p and q. Cracking an Internet code is therefore the same as cracking a number N into its prime building blocks. And as we saw in the section on flipping a coin over the Internet, this is virtually impossible when the numbers are big.
The Number Mysteries: A Mathematical Odyssey through Everyday Life (MacSci) Page 18