A Broken Record, Carl Zimmer

Discover, January 31, 1993

Mathematics is an ancient science. Yet even its simplest puzzles still mock us with their intractability. Take the problem of prime numbers. Primes are like elementary particles; they can’t be divided by any whole numbers except 1 and themselves. The numbers 2, 11, 19, and 10,957, for example, are all prime. Unfortunately, there’s no apparent pattern to the sequence of primes. Mathematicians have been trying to tease out a formula for finding a pattern since the days of Euclid, but to no avail. They’ve had to resort to making good guesses, then testing these prime candidates by trying to divide them into smaller numbers. If they can’t, a new prime joins the list.

Needless to say, this process is tedious and time consuming, even with supercomputers. If you programmed a computer to find all the prime numbers smaller than 20 digits just by dividing, you’d be dead centuries before it was through.

Which makes a mathematical record set this past year all the more remarkable. A Cray supercomputer at AEA Technology’s Harwell Laboratory in England broke the record for the largest known prime number: the new champ is 227,832 digits long–enough to fill about 30 pages of DISCOVER. (The previous record was a mere 65,050 digits.)

The software that ran the computer was written by Cray computer scientist David Slowinski, who is used to breaking prime number records; he’s done it five times since 1979. Like many number hunters, Slowinski focused on a certain group called Mersenne numbers, named after a seventeenth-century French monk who studied them for years. All Mersenne numbers take the form 2^(p)-1, where p is prime.

Mersenne numbers are appealing because they can be tested for primeness by applying a simple algorithm–a series of repeated steps, like a numerical dance, that zeroes in on a solution. (The way you learned to do long division in grade school is an algorithm.) The one Slowinski used goes like this: You start with a number; call it L. Square L, subtract 2, and then divide the new number by the Mersenne number. Take the remainder and plug it back into the algorithm as your new L. Start the process with L equal to 4, repeat it p-2 times, and if the last remainder you come up with is zero, then the Mersenne number is a prime.

Consider 31, which equals 2^(5)-1.

L = 4. 4^(2)-2 = 14. 14 divided by 31 = 0 with a remainder of 14.
L = 14. 14^(2)-2 = 194. 194 divided by 31 = 6 with a remainder of 8.
L = 8. 8^(2)-2 = 62. 62 divided by 31 = 2 with a remainder of 0.
L = 0. So 31 is prime.

For big primes, this procedure is far faster than factoring; still, it involves squaring numbers hundreds of thousands of times. To speed things up, Slowinski has incorporated increasingly faster multiplication shortcuts into his program. In the end it took his Cray-2 only 19 hours to check a number so big that even if all the subatomic particles in the whole universe were Cray computers and had been working since time began, they wouldn’t have had enough time to factor it, according to Slowinski. The new prime number is 2^(756,839)-1.

How do theorists get away with solving age-old puzzles on corporate time instead of, say, designing programs to help oil companies find new deposits? “There’s no one at Cray with the job description ‘Look for prime numbers,’ ” Slowinski says. His program is designed to put new supercomputers through their paces as well as to help show Cray’s customers how to improve software by means of the same techniques. “It’s like developing Buicks by testing cars on the racetrack. The race isn’t the ultimate goal.”