The prime number hunters close in 



The prime number hunters close in 
• 06 August 2005 
• From New Scientist Print Edition. Subscribe and get 4 free issues. 
• Ian Stewart 
• Ian Stewart is a mathematician and writer at the University of Warwick 
•

Enlarge image
Prime suspects 
Prime numbers are beautiful and fascinating - and an infuriating puzzle. Easy to define, yet rowdy and disordered, the primes have no evident pattern. The more of them you list, the more erratic they seem to be. 
Over the centuries, people have hunted for ways to find out which numbers are prime and which are not, and yet the best tests ever devised are so slow that even our ever-faster computers don't help much. A millionfold increase in computer speed just adds a few digits to the size of the numbers that can be handled. Mathematicians would dearly love a truly efficient way to find primes, and that needs brainpower, not computer power. 
At last, we are on the brink of such a test, thanks to the brains of Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena at the Indian Institute of Technology, Kanpur. And their work might mean more than just bigger game for prime-number hunters. Powerful codes based on primes are used to keep internet shopping and banking private and secure, and although the new test does not directly undermine the security of these codes, it hints that in the future our online dealings might be susceptible to an attack from an unexpected direction. 
The fatal fascination of the primes goes back a long way. In 1801, Carl Gauss, arguably the top mathematician of all time, said that the problem of distinguishing prime numbers from composite numbers is one of the most important in arithmetic. The primes are in a sense the atoms of number theory - the indivisible parts of all other numbers.
“A millionfold increase in computer speed just adds a few digits to the numbers that can be handled” 
A number is defined as prime if you can't get it by multiplying two smaller numbers together. So an obvious test for primality is just to try all possible divisors. You don't have to be a maths whiz to work out that 7 is prime, because none of the numbers 2, 3, 4, 5 or 6 divides 7 exactly. On the other hand, 6 = 2 × 3, so 6 is not prime. Then there are short cuts: you can rule out even numbers other than 2, because they are all divisible by 2. And you can stop when you reach the square root of the number you're interested in (if there's a divisor bigger than that, then there must also be one smaller). 
Trial division is all right in the classroom, to test numbers with only two or three digits. But it is completely hopeless for, say, a 100-digit number. The universe hasn't been in existence for as long as it would take to test all the possible divisors of a monster like that. Fortunately, other tests are possible. 
The crucial question is how fast a test will run, and the usual measure of this is how the running time increases with the number of digits in the number to be tested. If the time grows as a fixed power of the number of digits, that's good. Then the algorithm is in "class P", standing for polynomial time. Anything faster-growing is called "not-P". Trial division is firmly in the not-P class: testing a number with d digits that way takes a time proportional to 10d/2 (the square root of the number being tested). Time that grows exponentially like this is really bad - computational cloud cuckoo land. 
In 1956 the logician Kurt Gödel asked whether trial division could be improved on. He was eventually answered by the discovery of various practical methods for finding primes of around 100 digits or more, which have been known since about 1980. However, nearly all of these are probabilistic - they occasionally give the wrong answer, though that is extremely rare. 
Just one reliable test, discovered in 1983, lies tantalisingly close to P territory: the APR test, devised by and named after Leonard Adleman of the University of Southern California, Carl Pomerance of Bell Labs in Murray Hill, New Jersey, and Robert Rumely of the University of Georgia. It has a running time of d raised to the power ln ln d, where ln d is the logarithm of d. Technically, this algorithm is not-P, because the power keeps growing as d increases. But it grows very, very slowly - it is a mere 5.4 when d is 10100. (As the mathematicians' joke goes, it has been proved that ln ln d tends to infinity, but it has never been observed doing so.) 
Could there be a true class-P algorithm to test for primality? No one thought that was likely. No one had even found a way to get started on such a test - until Agrawal's group dropped its bombshell. 
Their idea emerged in 2002, when Kayal and Saxena were still undergraduates, and an improved version saw its first official publication early this year in Annals of Mathematics (vol 160, p 781). Their AKS algorithm is class P, and what's more it is novel and simple - to mathematicians, anyway. It is descended from the grandaddy of modern primality tests, Fermat's little theorem (not to be confused with its far more famous sibling, Fermat's last theorem). This is based on modular arithmetic, sometimes known as clock arithmetic because the numbers wrap round like those on a clock face. Pick a number and call it the modulus - in the clock example, it is 12. Then in any arithmetical calculation with whole numbers, you replace any multiple of 12 by zero. For example, 5 × 5 = 25, but 24 is twice 12, so 5 × 5 also equals "1 to the modulus 12". Modular arithmetic is very pretty, because nearly all of the usual rules of arithmetic still work - except that some non-zero numbers vanish.
“Any failure to understand the prime numbers leaves nasty holes in the fabric of mathematics” 
Fermat's little theorem says that if you choose a prime modulus, it has a special property: one particular simple formula is always equal to 1. (If you're interested, the formula is a(p - 1), where p is the modulus and a is any number that's not a multiple of p.) If the answer to the formula is not 1, then the modulus you chose isn't prime. So the theorem can form the basis of a test that any prime must pass. The test is not perfect, as many non-prime numbers pass it too, but there are more sophisticated variants of Fermat's little theorem that can be turned into genuine tests for primality. The most efficient of them is the APR test. 
Agrawal's team came up with a variant on this idea. Instead of working with numbers, they use a polynomial - an algebraic expression. The idea came from a 1999 paper by Agrawal and his PhD supervisor Somenath Biswas, which gave a probabilistic test for primality based on such polynomials. Agrawal was convinced that the probabilistic element could be removed. Late in 2001 his two students Kayal and Saxena came up with a crucial, rather technical, observation. At first it led the team into deep number-theoretical waters, but eventually everything was reduced to a single obstacle. Their algorithm would only work if a special prime p always exists within a certain range of numbers related to the number being tested. The special aspect is that that p - 1 must have a very large prime divisor. After asking around, and a bit of googling, they found that in 1985 Étienne Fouvry of the University of Paris XI had shown just that. The final piece of the puzzle slotted neatly into place: their algorithm worked. 
As it stands, the AKS method is impractical. The original version had running time proportional to the number of digits raised to the power 12, and although its latest incarnation has improved that to 7.5, that will only beat APR when the number of digits is about 101000. There isn't room to fit a number that big into a computer's memory, or, indeed, into the known universe. But now that we have a class-P algorithm for primality testing, it becomes worthwhile to look for better ones. Already, Pomerance and Hendrik Lenstra of the University of California, Berkeley, have reduced that 7.5 to 6, using the same overall strategy as the Kanpur trio, but different tactics. If various other conjectures about primes are true, then the running time can be reduced to d to the power 3, which starts to look practical. Primes of a thousand digits or more could become child's play. 
But to mathematicians, the most exciting aspect of the AKS algorithm is the method. Prime numbers are absolutely fundamental to mathematics, and any failure to understand them leaves nasty holes in its fabric. AKS has, if not filled in those holes, at least given mathematicians a better idea of where they are. The algorithm and its variants all rely on the existence of prime numbers with specific properties, and often the method requires detailed information about how these special primes are scattered among the other numbers - the detailed geography of the prime number landscape. AKS has taught us that particular features of that landscape are important, and we don't know as much about them as we would like. 
In the days when number theory was tucked away in its own little ivory tower, none of this would have mattered much to the rest of the world. But over the past 20 years, prime numbers have become important in cryptography, the science of secret codes. Codes aren't just important for military use; commercial organisations want to encode their secrets too, and in this internet age, we all do. We don't want criminals to gain access to our bank accounts, our credit card numbers, or, with the growth of identity theft, the name of our pet or granny's shoe size. But the internet is such a convenient way to pay bills, insure cars and book holidays that we are willing to take the risk of crucial information falling into the wrong hands. 
Computer manufacturers and internet service providers try to reduce that risk using encryption systems. One of the most important, the RSA system, is based on prime numbers - big ones, about a hundred digits long. The RSA system is employed in most computer operating systems, built into the main protocols for secure internet communication, and widely used by governments, corporations and universities. It has been licensed to more than 700 companies, and half a billion copies have been installed worldwide. 
To break RSA, you would need to be able to find the factors of numbers with 200 or more digits. Although factorising a number is generally harder than testing it for primality, the two problems are related, and mathematicians use the same set of tools for both of them. 
All this adds a frisson of excitement to any discovery that relates primes to computation. There was one such flutter of interest in 1995, when Peter Shor of Bell Labs proved that there is a class-P algorithm for factorisation. Fortunately, perhaps, it needs a quantum computer to run on, a piece of hardware that exists only in theory. 
And now Agrawal's test has cast RSA cryptography in a new and slightly disturbing light. We now know that primality testing can be done efficiently, using ordinary computers. Is there a class-P algorithm for finding the factors of a non-prime number? Most experts think the answer is "no" - but that's what they were saying about prime testing not long ago. Now they're not quite as sure as they used to be about factorisation. If it is "yes", then the RSA cryptosystem is insecure. 
A mitigating factor is that RSA is not used to send entire messages, but just to transmit relatively short "keys" that make other, more traditional encryption systems possible. Any would-be codebreaker would have to be a cunning spy already to intercept and identify the key.
“We have to worry that cryptosystems may not be as secure as we fondly imagine” 
So the implications of AKS for cryptography are suggestive: be careful. If new discoveries like the AKS algorithm can lurk in the wings, then we have to worry that current cryptosystems may not be quite as secure as we fondly imagine. Don't reveal your cat's name on the internet just yet.
From issue 2511 of New Scientist magazine, 06 August 2005, page 40 
Record-breakers 
For 2500 years, mathematicians have known that there are infinitely many primes. So it's no surprise that the record for the largest known prime keeps growing. These days, it is regularly broken - the last time by a German doctor, Martin Nowak, on 18 February. His record-breaker is 225,964,951 - 1, which has 7,816,230 digits. 
That is far larger than the 100-digit midgets that are the limit for general prime tests. How, then, do we find out that these enormous numbers are prime? The answer is that super-fast tests can be tailored to take advantage of the special characteristics of these numbers. 
For many years, almost all record-breaking primes have been "Mersenne numbers", of the form 2p - 1, where p is itself a prime. They're named after the French monk Marin Mersenne (1588-1648), who in 1644 found some of the smaller ones, a nnouncing that for example 231 - 1 is prime, as is 2257 - 1. 
Mersenne numbers are susceptible to a special algorithm called the Lucas-Lehmer test, which is the basis for the "great internet Mersenne prime search" (GIMPS). You can download software that will use your computer's spare CPU time to look for Mersenne primes and send the results to a central site. Nowak's record-breaker was found this way. Proving it prime took more than 50 days of calculations on a Pentium 4 - lightning fast, considering the size of the number. 
To join GIMPS, visit www.mersenne.org. A new record has negligible actual mathematical significance, but you might have the satisfaction of scaling the highest peak yet known in the landscape of the primes. 

Posted: Tue - August 30, 2005 at 11:32 PM          

©