Forget the excitement and mystery of Fermat’s last theorem, the result announced in  2002 by Agrawal, Kayal, and Saxena, of the Indian Institute of Technology in Kanpur solves one of the oldest and most important problems in pure mathematics – how to test if a number is prime or not.

The three people who solved the primality testing  problem in 2002.

They simultaneously sent a wave of amazement through the mathematical world and a shudder through the world of spys and spooks.

The reason for the amazement is that solution to the problem doesn’t use brand-new advanced methods but a fresh approach to the problem. The reason for the shudder is that the whole of our digital security, codes, signatures and certificates, depends on the pure mathematics at the heart of the primality problem.

Factoring and codes

Before going on to explain the new ideas it helps to put the whole thing in context of why it is of practical importance in computing.

The entire security of the Internet and much desktop computing is based on the PKI, or Public Key Infrastructure. This allows two users, or machines, who have never met before to establish secure communication without any real possibility that a third party can eavesdrop.

The basis of this method is the use of two numeric keys - a public key which can be used to code a message which can only be read with the use of another key, the private key. This is now such a commonplace that it is possible to miss how odd the idea is.

You have a mathematical algorithm based on a key that mixes up data that can only be undone easily if you have another key.

All of this seems very abstract and explaining it in all its detail would take some time, but there are simpler examples that illustrate the basis of the PKI.

For example, suppose Bob wants to send the serial number of a luggage locker to Alice, then one simple way to do it is to send a number which is the product of the locker number and another number – the key.  Bob might use a key picked at random but smaller than 10,000 to encode the locker number and send Alice:

     137703491

Now all you have to do to crack Bob’s code is to find two numbers which multiply to give 137703491. You might think that this was easy but the only way to do it is to start off with 2 and work your way through all the possibilities until you find something that divides it exactly.

Of course there are shortcuts. For example once you have checked that it isn’t divisible by 2 you don’t have to check 4, 6, 8 and so on, but there is still enough checking to keep you busy and more importantly the work involved increases in an unreasonably demanding manner as the size of the number goes up. So factoring 143, a three-digit number, is easy enough but factoring 137703491, a nine-digit number, is far more than three times more difficult. What this means is that no matter how good computers get at factoring Bob can just pick a bigger pair of numbers to multiply together.

In the jargon multiplication is a “one-way function” because undoing it is harder than doing it.

How does Bob get the information out?

Easy - since he chose the key he knows that it is 7919 and if you also know this you can get the locker number back by simple division:

      137703491/7919 

gives you the locker key.

If you find this example unconvincing tell me what two numbers multiply together to give:

     7621615238978741781241003

(Answer at the end of the article)

Public key cryptography is based on similar, but slightly more involved methods, for factoring a number but it is worth knowing that many schemes would be easy to break if anyone could find an easy way of factoring large integers.

Primes

Now to return to our main subject – prime numbers. Primes are special in the world of integers because they are numbers that do not have any non-trivial factors. In fact we have already made use of two primes in the locker number example. Most numbers have multiple factors and yet I claimed that 137703491 had exactly two factors – the key and the locker number. The reason I could be so sure is that the key used is a prime, i.e. it has no other factors, and the locker number was chosen, conveniently, to be another prime. I can generate similar puzzles by taking two primes and multiplying them together safe in the knowledge that the result has just two factors – i.e. the only primes I used.

Large prime numbers are used to generate codes and they have grown increasingly important for this very reason. However, they fascinated mathematicians for many years before they became famous in this context. The interest has been high since early times. For example the Greek mathematician Euclid showed that there were an infinite number of primes and since then there have been many questions asked about these mysterious numbers that have no factors, such as how many primes are smaller than a given upper limit, what is the probability that a number chosen at random has just two prime factors and so on.

<ASIN:0385495323>

<ASIN:3540430725>

<ASIN:0387772677>