custom search of this site
	Newspaper story on 2^1257787-1 is prime
	[chongo's home] [Astronomy] [Mathematics] [Prime Numbers] [Programming] [Technology] [contacting Landon]

Note: This is no longer the largest known prime

CRUNCHING NUMBERS
RESEARCHERS MAKE PRIME MATH DISCOVERY

BY DAN GILLMOR, Mercury News Computing Editor

When the British mountaineer George Leigh Mallory was asked why he wanted to scale Mount Everest, he replied: ''Because it's there.''

A related urge sparks computer scientists at Silicon Graphics Inc.'s Cray Research unit, who will announce today that they've discovered the world's largest-known prime number - and a special kind of prime number at that. This one is 378,632 digits long, roughly 120 single-spaced typewritten pages - and ''a rare jewel,'' said co-discoverer Paul Gage.

But the way they found it, using sophisticated programming on high-powered supercomputers, goes well beyond mathematical mountain climbing. The techniques help create and test computer systems that in turn help solve real-world problems such as cryptography, improving weather forecasts and designing safer cars, said David Slowinski, the other co-discoverer of the latest record number.

Using a Cray T94 supercomputer, Slowinski and Gage found what is currently the biggest example of a Mersenne prime number, named after a 17th-century French monk, Father Marin Mersenne, who had a thing for numbers. A prime number is an integer greater than zero whose divisors are only itself and 1. (The number 2 is prime because it can only be divided evenly by 1 and 2, for example). Mersenne numbers are primes that take the form 2 to some power, minus 1 - in other words, 2 multiplied by itself a certain number of times with 1 subtracted from the result.

The smallest Mersenne prime is 3, or 2 to the 2nd power (2x2=4) minus 1. The next largest ''regular'' prime number is 5, and the next largest Mersenne prime is 7, or 2 to the 3rd power (2x2x2=8) minus 1. Two to the 4th power (16) minus one equals 15, not a prime number since it can be divided by 1, itself, 3 and 5. But 2 to the 5th power (32) minus 1 - 31 - is a Mersenne prime.

Not their first

The latest discovery - only the 34th known Mersenne prime - is 2 to the 1,257,787th power (2 multiplied by itself 1,257,787 times) minus 1. The previous largest-known Mersenne prime, 2 to the 859,433rd power minus one, was discovered by Slowinski and Gage in 1994. Slowinski has been a Mersenne discoverer or co-discoverer seven times. This is Gage's third co-discovery.

One elegant oddity about Mersenne primes is a mathematical connection to other intriguing integers. For every Mersenne prime, there's a corresponding (but larger) ''perfect number,'' a class of integers that fascinates mathematicians. Perfect numbers are equal to the sum of all of their positive divisors, except themselves; for example, 6 is a perfect number (1+2+3=6).

Back to Euclid

Perfect numbers and what later came to be called Mersenne primes date actually back to the legendary Greek mathematician, Euclid, said Carl Pomerance, professor of mathematics at the University of Georgia in Athens. It was Euclid who noticed the connection. Later, Mersenne spent years looking for the integers that now bear his name.

''In modern days,'' Pomerance said, ''they've become a benchmark for computers.''

Silicon Graphics is a hotbed of prime-number research. People who work at SGI or its subsidiaries have been involved in the discovery of the last 10 record-setting primes, according to Landon Curt Noll, a cryptographer and member of Information Security Infrastructure Team at the Mountain View-based company. Noll has held or shared the Mersenne record twice. Slowinski works at Cray's Chippewa Falls, Wis., manufacturing plant. Gage is based at Cray's headquarters in Eagan, Minn.

One purpose of the Mersenne testing is to put new Cray machines through the paces before sending them to customers. Slowinski and Gage have ''a lot of fun, but they really are doing the company a service,'' said Cray spokeswoman Mardi Larson.

The computer scientists' latest Mersenne discovery occurred last spring. As is customary, they asked independent researchers to double-check their work before making it public.

Competitor checks it

One tester was George Woltman, a programmer in Florida who has been hunting for Mersenne primes from a different direction. He and about 400 volunteers around the world have been searching systematically using PCs powered by Intel Corp. Pentium processors. They need as many machines as they can get; just one Cray processor checked the latest Mersenne prime in about six hours, but a 90-megahertz Pentium took more than 60 hours.

Woltman said he was about 90 percent of the way through the very number that Slowinski and Gage found when they told him about their discovery and asked him to double-check it.

''It hurt for a few days, but I got over it,'' he said. ''It doesn't diminish my enthusiasm. We'll never run out of exponents to check.''

For more information on the latest Mersenne prime, point your World Wide Web browser to http://www.isthe.com/chongo/tech/math/prime/prime_press.html. For more information on George Woltman's project to use PCs in the search, point your browser to http://www.mersenne.org. And if you really want to see what the largest-known prime number looks like, point your browser to http://www.isthe.com/chongo/tech/math/prime/m1257787.html.

Copyright 1996, The San Jose Mercury News. Unauthorized reproduction prohibited.

Note: This is no longer the largest known prime