Page 1 of 2
Testing to see if a number is a prime or not is the basis of many encryption and security methods. It has long been assumed that there is no fast way, i.e no polynomial time method, to determine if a number is prime, but now we know different. It is lesson to us all that a classic problem that was long thought not to have a polynomial solution does indeed have one. Given that we rely on some of these problems to keep our secrets safe, this is a change in perspective.
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.
We are assuming that the locker number and the key are prime numbers which, in the locker's case is unlikely. There are ways around the problem for example Bob could add a message to Alice that his locker number was 145 less than the smallest factor.
Bob might use a prime key picked at random but smaller than 10,000 to encode the locker number and send Alice:
Now all you have to do to crack Bob’s code is to find two prime 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 (11 time 13) 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:
gives you the locker key.
If you find this example unconvincing tell me what two numbers multiply together to give:
(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.
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.
The question that is of most interest to cryptographers is very similar to the factoring problem discussed earlier. If I give you a number can you tell me if it is a prime or not. Clearly to prove that it’s not a prime all you have to do is find a non-trivial value, i.e. not 1 or the number itself, that divides it exactly. On the other hand to prove that it is a prime means you have to test all of the possible candidates for dividing it and show that none of them actually do.
Clearly primality testing is difficult. In fact Eratosthenes in 200BC developed the first of the primality testing algorithms but it has the problem of being slow.
His method “The Sieve of Eratosthenes” works like this:
- Suppose you want to test n for primality
- Make a list of numbers from 2, to n and begin by putting a circle around 2 and then crossing off all of its multiples
- Next move to 3 and put a circle around it and cross off all its multiples and so on
- When you have finished and every number is either crossed off or circled all you have to do is to see if any of the circled numbers divide n
- If none of them do then n is a prime
This works because all of the circled numbers are primes and this is the smallest set of numbers we need to test to see if n is also prime.
This algorithm works but it’s slow and it gets slower as n gets bigger. It simply isn’t a practical method of testing primes.
The problem solved in 2002 is whether or not there is a quick method of testing if a number is prime – to be more precise whether primality testing is something that can be done in polynomial time, in other words in a time that increases only like some power of the size of the number n.
Until the discovery of the new algorithm all primality tests took longer than polynomial time and hence weren’t practical once n got sufficiently big.
The AKS algorithm found by Agrawal, Kayal, and Saxena is most simply put as “Primes is in P”.
The 13-line program that tests numbers for primality with certainty faster than any other