Prime numbers, beautiful and useful

Dear readers,

As my second interview had to be delayed due to the holidays, I am going to tell you instead about a topic that has always fascinated me by its simplicity, beauty and at the same time usefulness in real life. That topic is prime numbers. I will begin by describing some relevant theoretical results, then explain how they form the basis of modern online security, and then briefly discuss how quantum computers – if they ever come into existence – would force us to redesign a large number of our security systems.

First, let me remind you what prime numbers are. They are the numbers that are only divisible by 1 and themselves. Their sequence begins with 2, 3, 5, 7, 11, 13 and never ends, as the Ancient Greeks already knew. Indeed, if we supposed there were only finitely many of them, we could multiply them all and add 1 to get a result which would be larger than any of them, yet not divisible by any (because of the 1), leading to a contradiction. This proof technique is called reductio ad absurdum. In fact, the great Dirichlet showed that there are infinitely many primes in any arithmetic progression (a sequence you start with a number, called the first term, and keep adding another number, called the difference – for example, if the first term is 2 and the difference 3, you get 2, 5, 8, 11, etc), as long as the first term and the difference are integer and have no common factors. In 2004, Ben Green and Terry Tao showed that there are in fact arbitrarily long sequences of consecutive primes in arithmetic progression (a different and somewhat more surprising result because of the requirement that the primes be consecutive).

So what makes the primes important? They are the building blocks from which all integers are made. As you may remember from grade school, every integer can be factored into primes – and not only that, but this factoring is unique except for the order. The second property is not always true in other number systems. And now we get to the crux of the modern cryptographic protocols. While checking that a given number is prime is easy (fast on a modern computer), and multiplying numbers is easy as well, factoring an integer that is composed of as few as two primes can be hard (even with a supercomputer).

How can we check that a number is prime? There are some properties that a prime number satisfies, and few composite numbers satisfy them. One such property comes from Fermat’s little theorem, not to be confused with Fermat’s (in)famous last theorem, which states that if p is prime then ap-1-1 is divisible by p for any a between 1 and p-1. On the other hand, it turns out that if p is not prime, then fewer than half of all the possible bases a between 1 and p-1 still satisfy this property (such numbers p are called pseudoprimes to the base a), unless you happen to be very unlucky. So, by performing a number of tests with random bases one can determine with a great degree of confidence whether a given number p is prime. This approach is an example of a probabilistic algorithm, one which gives the right result with high probability if repeated many times. Interestingly, the first fast deterministic (not chance-based) algorithm for testing primality was found only in 2002, by two undergraduate students at the Indian Institute of Technology Kanpur, Neeraj Kayal and Nitin Saxena, and their advisor, Manindra Agrawal.

If you’ve watched a security certificate being generated on your computer (which generally takes a few seconds, depending on the certificate’s “grade”), here is exactly what happens – it produces two large numbers, checks that they are both prime (there are enough prime numbers to go around – if you want a 128-bit number you need to check about 100 candidates on average, by the prime number theorem) and multiplies them together. This gives you your “public key”, which you can share freely with the world. It allows other people to send you messages by encrypting them with your public key; however, since getting the original two prime numbers from your public key is hard (only your computer knows them because it generated them in the first place), you are the only one who can actually decrypt them!

This, in a nutshell, is the RSA system, named for MIT researchers Rivest, Shamir and Adleman. They are given the credit for publishing it first, but it had already been known to Clifford Cocks who, however, could not publish it because he worked for the British intelligence. Public-key cryptography was a revolutionary advance in technology – now you no longer need to worry about your encrypted messages being intercepted, because decrypting them is all but impossible – but it relies on the fact that factoring large numbers is hard. We believe that this is true with ordinary computers, though we cannot prove it for sure. This is where yet another surprise came in 1994: Shor’s quantum factoring algorithm!

Without going into details about quantum computers, let me just say that they are a very special mode of computation which relies on the quantum states of particles. While a regular bit has only two states, 0 and 1, a quantum bit (qubit for short) can exist in a superposition of these states (for an idea of what superposition is, think about two different sound frequencies you can hear at once), and only when it’s measured does it collapse to a well-defined state (the so-called collapse of the wave function). Now, it turns out that some things that are difficult to do on a regular computer are easier on a quantum one. And factoring large numbers just happens to be one of those things, as shown by Peter Shor in 1994. It is another probabilistic algorithm, and only requires a quantum computer large enough to write down the integer to be factored twice. For instance, for numbers of the size we discussed, this is 500 qubits.

Where does this leave us and our security systems? Well, on the one hand, quantum computers are still in their infancy as far as the technology goes (this is one field where theory has far outpaced practice), and the largest one in existence today cannot factor numbers greater than 100. On the other hand it may well happen that the technology will one day evolve to being able to build large quantum computers, so that all our security systems will be easily broken. If that happens, it may be necessary to also use quantum computers for building new security systems. Meanwhile, there are alternative systems being developed such as elliptic curve cryptography (the same elliptic curves used by Wiles to prove Fermat’s last theorem, which are plane curves defined by the equation y2 = x3 + ax + b). Perhaps not surprisingly, they also rely on prime numbers – but in a rather different way. Namely, they are based on counting the remainders that points on the elliptic curve can have when they are divided by a prime number.

Godfrey Harold Hardy, author of the famous and delightful book “A mathematician’s apology”, spent most of his life working on prime numbers (including the notorious and still unresolved Riemann hypothesis), prided himself on the lack of practical applications of his work. He notably said, I have never done anything ‘useful’. No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world”. Ironically, some of his work on prime numbers has turned out to be quite useful, and in my opinion, it is a credit to mathematicians, both pure and applied, that such a beautiful topic has also found such important applications in our everyday life.