Prime movers and shakers

THAT'S MATHS:PRIME NUMBERS are of central importance in pure mathematics and also in a wide range of applications, most notably cryptography. The security of modern communication systems depends on their properties. Recall that a prime number is one that cannot be evenly divided by a smaller number. Thus 2, 3 and 5 are primes, but 4 and 6 are not, since 4 = 2 x 2 and 6 = 2 x 3. Primes are the atoms of the number system: every whole number is a product of primes.

The search for patterns in the distribution of primes has occupied mathematicians for centuries. They appear to be randomly strewn among the whole numbers, but there are tantalising indications of structure. Often, a hint of a pattern emerges, only to evaporate upon further study. Thus, 31 is prime, as are 331, 3331, 33331 and the next three members of this sequence. But 333,333,331 is divisible by 17, and the pattern is broken.

In elementary algebra, we learn to solve quadratic equations. This corresponds to finding the zeros of a simple polynomial equation. The zeros of a more complicated function, called the zeta function, are intimately connected with the distribution of the prime numbers, but the location of all these zeros is enormously difficult. They are believed to satisfy a pattern first proposed in 1859 by Bernhard Riemann but this has never been proved. The Riemann hypothesis is widely regarded as the most important unsolved problem in mathematics. A proof would have far-reaching implications and whoever proves it will win lasting fame. They will also collect a $1 million (€770,000) prize from the Clay Mathematics Institute.

The frantic dash to find ever-larger prime numbers has been dominated in recent years by the Great Internet Mersenne Prime Search (Gimps), a voluntary collaborative project involving a large number of personal computers. The record for the largest prime is broken on a regular basis. Almost all the recent examples have been found by Gimps, and are numbers of a particular form called Mersenne primes, which are one less than a power of 2. The current record prime, found in 2008, can be obtained by multiplying 2 by itself 43,112,609 times and subtracting 1. It has more than 12 million decimal digits. To print it would require several thousand pages of this newspaper.

Mersenne numbers take their name from a 17th-century friar called Marin Mersenne. Born in France in 1588, Mersenne was a strong apologist for Galileo, whose scientific ideas challenged religious orthodoxy. Mersenne’s main scientific work was in acoustics, but he is remembered today for his association with the Mersenne primes. He had contact with many mathematical luminaries, and provided a vital communication channel, corresponding with mathematicians, including René Descartes and Étienne Pascal, in many countries. Mersenne was, in essence, a one-man internet hub.

So far, Gimps has found a total of 13 Mersenne primes, repeatedly smashing the record. The project uses a search algorithm called the Lucas-Lehmer primality test, which is particularly suitable for finding Mersenne primes and is very efficient on binary computers. The test was originally developed by Édouard Lucas in the 19th century, and improved by Derrick Henry Lehmer in the 1930s.

For discovering a prime with more than 10 million decimal digits, Gimps won a $100,000 prize, and a Cooperative Computing Award, from the Electronic Frontier Foundation. A prize of $150,000 is on offer from the foundation for the first prime number found with at least 100 million decimal digits, and a further $250,000 for one with at least a billion digits. What are you waiting for?

Peter Lynch is professor of meteorology at University College Dublin. He blogs at thatsmaths.com