Professor Stewart's Hoard of Mathematical Treasures (12 page)

It can be proved that division does make sense whenever the modulus is prime, though you still can’t divide by 0. For instance, if the modulus is 5, then the two tables above become
Every number appears in every row of the multiplication table, except row 0, and we can now say things like
because
Again, the usual rules for division also work in these cases.

When there is any danger of confusion, mathematicians write these equations like this:
with a special symbol ≡ replacing the equals sign, and a reminder of which modulus is involved, to make it clear that they don’t really think that 2×4 = 3. But often they don’t bother.

Arithmetic to a modulus is the key (no pun intended) to a remarkable development in cryptography: the public key cryptosystem. All codes rely on secret keys, and the biggest danger is that an eavesdropper finds out what the key is. If the enemy gets hold of a copy of your one-time pad, perhaps through the actions of a spy, you’re in deep trouble.

Or maybe not. The tacit assumption here is that, once someone knows the key, they can easily decode the message. After all, that’s what the intended recipient has to do, so it’s silly to make it hard. But in 1977 Ron Rivest, Adi Shamir and Leonard Adleman discovered that matters aren’t quite so straightforward. In fact, it is possible to make public the key for putting a message into code, without anyone being able to deduce the inverse procedure of decoding the message. However, the legitimate recipient can decode the message using a different, related key - which is kept secret.

Methods like this rely on a curious mathematical fact: reversing a calculation, working back from the answer to the question, can sometimes be much harder than doing the calculation itself - even when the process is in principle reversible.
¹³
If so, knowing the procedure concerned does not make it possible to work out how to undo it. But this fact alone is no use unless there is some secret short cut, so that the intended recipient can undo the encoding procedure easily. And it is here that arithmetic to a modulus, Gauss’s bizarre invention in which 2 + 2 might be 0, comes into its own.

The RSA cryptosystem, named after the initials of its aforementioned inventors, is based on a theorem proved by Euler, generalising a simpler one discovered and proved by Pierre de Fermat. The simpler version is called Fermat’s Little Theorem, to distinguish it from his Last (or ‘Great’) Theorem (Cabinet, page 50). It states that if you are working to a prime modulus p, then
a
^p-1
≡ 1 for any number a. For example, with 5 as the modulus, we should find that 1
⁴
≡ 1, 2
⁴
≡ 1, 3
⁴
≡ 1, 4
⁴
≡ 1. And they are. For instance,
because 81 - 1 = 80, which is divisible by 5. The same sort of thing works for the other numbers.
¹⁴

To apply RSA encryption, you first represent messages by numbers. For example, every block of 100 letters, spaces and other characters could be represented as a 200-digit number,
where each successive pair of digits encodes characters according to the rule A = 01, B = 02, . . . , Z = 26, [space] = 27, ? = 28, and so on. Then a message breaks up into a series of 100-digit numbers. Let N be one of those numbers. Our first task is to put N into code, and we do that using a mathematical recipe in modular arithmetic.

I’ll start with an example, using numbers much smaller than those used in practice.

Alice uses two special numbers: 77 and 13, which can be made public. Suppose that her message is
N
= 20. Then she calculates 20
¹³
(mod 77), which is 69, and sends that to Bob.

Bob knows the secret number 37, which reverses what Alice does with 13. He decodes Alice’s message by raising it to that power (mod 77):

This works for any message that Alice might send, because
Where do these numbers come from?

Alice’s choice of 77 is the product of two primes, 7×11. Euler’s theorem applies to the number (7 - 1) × (11 - 1), which is 60. It tells us that there is some number d such that 13
^d
≡ 1 (mod 60), and then (
N
¹³
)
^d
≡ N (mod 77) for any message N. As Bob - and only Bob - knows,
d
= 37.

To make this method practical, we replace 7 and 11 by much larger primes - typically with 100 digits or thereabouts (see note on page 288). The encoding key (here 13) and decoding key (here 37) can be calculated from those primes. Only the encoding key and the product of the two primes, a 200-digit number, need be made public. Only Bob need know the decoding key.

This involves finding really big primes, which turns out to be easier than we might expect: there are efficient ways to test whether a number is prime without looking for factors. And, of course, you have to use a computer to do the sums. Note the catflap effect: Alice doesn’t need to know how to decode
messages, only how to encode them. Mathematicians generally think, but can’t yet prove, that working out the prime factors of a really big number is extremely hard - so hard that in practice it can’t be done, no matter how big and fast your computer might be. Finding big primes is much easier, and so is multiplying them together.

Of course, in my example, with impractically small numbers, finding the decoding key 37 is easy. Alice could work it out, and so could any eavesdropper. But with 100-digit primes, say, calculating the decoding key seems to be impossible if all you know is the product of the two primes. On the other hand, if you do know the primes, then it is relatively straightforward to find the decoding key. That’s why it’s possible to set up the system to begin with.

Systems like RSA are very suitable for the internet, where every user has to ‘know’ how to send an encrypted message (such as a credit card number). That is, the method for encrypting this message has to be stored on their computer. So a skilled programmer could find it. But only the bank needs to know the decryption key. So until criminals discover efficient ways to factorise big numbers into primes, your money is safe. Assuming it’s safe in the hands of the banks, which has suddenly become questionable.

In practical applications, some care has to be taken and the method isn’t quite this simple. See, for example:
en.wikipedia.org/wiki/RSA

It is also worth remarking that, in practice, RSA is mainly used for sending encrypted versions of keys to other, simpler cryptosystems, which can then be used to send messages, rather than using RSA for the messages themselves. RSA involves a bit too much computational time to be used routinely for messages.

There is a curious historical postscript to this story. In 1973, the same method was invented by Clifford Cocks, a mathematician working for British Intelligence, but it was considered impractical at the time. Because his work was
classified Top Secret, no one knew about his anticipation of the RSA system until 1997.

‘My beautiful assistant,’ stated the Great Whodunni, ‘will now hand me a perfectly ordinary calendar.’

Grumpelina smiled sweetly and did as instructed. It was indeed an ordinary calendar, with seven columns per month, headed by the days Sunday-Saturday, and the numbers of the days written in order.

Whodunni then called for a volunteer from the audience, while Grumpelina blindfolded him (Whodunni, that is).

‘I want you to choose any month from the calendar, and then draw a 3×3 square round nine dates. Don’t include any blank spaces. I will then ask you to tell me the smallest number from those dates, and I will instantly tell you what the nine numbers add up to.’

The volunteer did so, and, as it happened, he chose a square of dates for which the smallest number was 11. As soon as he told the magician this number, Whodunni immediately replied ‘171’.

Whodunni’s method works whichever 3×3 square is chosen. How does he do it?

 

Answer on page 289

The volunteer’s choice.

Isaac Newton, it is said,
¹⁵
had a cat. He cut a hole in the bottom of his study door so that puss could get in and out. So we must add to Newton’s achievements the invention of the catflap, except that his version lacked the flap. Anyway, the cat had kittens. So Newton cut a small hole in the door next to the bigger one.

I don’t know whether Lewis Carroll - pen-name of the mathematician Charles Lutwidge Dodgson - had a cat, but he created one of the most memorable fictional cats: the Cheshire Cat, which slowly faded away until only its grin remained. The Cheshire isn’t a breed of cat: it is an English county where cheese was (and still is) made. Possibly Carroll was referring to the British shorthair, a breed of cat that appeared on Cheshire Cheese labels.

The Cheshire Cat.

Problem 79 of the ancient Egyptian Rhind Papyrus (pages 77-8) poses the sum
where each number is 7 times the previous one. The scribe gives a short cut:

Note that 2,801 = 1 + 7 + 49 + 343 + 2,401. These numbers are the first few powers of 7. I have no idea why the scribe thought it sensible to add up such diverse items, mind you.

Still on exponential growth: the Humane Association has pointed out that if two cats and their kittens breed for 10 years, with each cat having two litters of three surviving kittens per year, then the cat population grows like this: