A Prime of Record Size! 21257787-1

By Chris Caldwell

Slowinski, Cray T94, GageOn 3 September 1996, Cray Research announced that once again Slowinski and Gage have set a new record by finding the prime 2^1257787-1 which has 378,632 digits. This is the largest known prime by far--the next largest has "only" 258,716 digits. It is also the 34th Mersenne prime to be discovered (though it might not be the 34th in order of size as the entire region below it has not been checked). Looking at the graph of the largest known prime by year, we see this prime is roughly the size record we'd expect to find this year.

The proof of this 378,632 digit number's primality (using the traditional Lucas-Lehmer test) took about 6 hours on one CPU of a CRAY T94 super computer. Richard Crandall and others independently verified the primality. The first and the most interesting of these was George Woltman who was 90% of the way through that very number when asked to check the result on April 15th. According to the San Jose Mercury News article he said "It hurt for a few days, but I got over it." Woltman's program is available over the Internet and will check this new prime in about 60 hours on a 90MHz Pentium.

Finally, 16*1257787+1 divides (2^1257787+1)/3, so again the "new mersenne prime conjecture" satisfied.

Below is the official announcement from Steve Conway (Media Relations Manager) of Cray Computers (with a few corrections). Here are several related pages.

(Note: Cray Research is now a wholly owned subsidiary of Silicon Graphics)


[Notes in brackets added by Chris. These errors were not caused by Slowinski and Gage; they are solely the creation of the public relations folk at SGI.]

Employees of New Combined Silicon Graphics, Cray Responsible For Nearly All [Mersenne] Prime Discoveries in Last 20 Years

EAGAN, Minn., September 3, 1996 -- Computer scientists at Cray Research have discovered the largest-known prime number while conducting tests on a CRAY T94 system, one of the company's latest supercomputers, at its Wisconsin engineering and manufacturing operation in Chippewa Falls.

The new prime number is the 34th [Mersenne] discovered and has 378,632 digits. Printed in newspaper-sized type, the number would fill approximately 12 newspaper pages.

The largest Mersenne prime previously known was discovered in January 1994 also at Cray Research's Wisconsin operation by the same computer scientists once again conducting rigorous quality tests of a Cray supercomputer. That prime number had 258,716 digits.

Cray officials said that seven of the last eight Mersenne prime discoveries were run on Cray Research supercomputers. According to Cray, which recently merged with Silicon Graphics, Inc., Mountain View, Calif., all but one of the Mersenne prime number discoveries over the past 20 years were lead by Silicon Graphics or Cray employees [but not necessarily employees at the time of the discovery: Curt Noll who now works for Silicon Graphics, was a high school student using a CDC Cyber 174 computer at the time of his discoveries].

A Prime Lesson

In mathematical notation, the new prime number is expressed as 2^1257787-1, which denotes two, multiplied by itself 1,257,787 times, minus one [actually 1257786 times, minus one]. Numbers expressed in this form are called "Mersenne" prime numbers after Father Marin Mersenne, a 17th century French monk who spent years searching for prime numbers of this type.

Prime numbers can be divided evenly only by themselves and one. Examples include 2, 3, 5, 7, 11 and so on. The Greek mathematician Euclid proved that there are an infinite number of prime numbers. But these numbers do not occur in a regular sequence and there is no [useful] formula for generating them. Therefore, the discovery of new [Mersenne] primes requires randomly [??] generating and testing millions [tens of thousands] of numbers.

"Finding these special numbers is a true 'needle-in-a-haystack' exercise, but we improve our odds by using tremendously fast computers and a clever program," said David Slowinski, a Cray Research computer scientist. Slowinski and fellow Cray Research computer scientist Paul Gage developed the program that found the new prime number. Mathematician Richard Crandall, Ph.D., [and George Woltman] independently verified the Cray team's prime number discovery.

Practical Applications Of Prime Numbers

Prime numbers have applications in cryptography and computer systems security. Huge prime numbers like those discovered most recently are principally mathematical curiosities, but the process of searching for prime numbers does have several practical benefits.

For instance, the "prime finder" program developed by Slowinski and Gage is used by Cray Research as a quality assurance test on all new supercomputer systems. A core element of this program is a routine that involves squaring a number repeatedly. As this process continues, it eventually involves multiplying immense numbers -- numbers of hundreds of thousands of digits -- by themselves.

"This acts as a real 'torture test' for a computer," said Slowinski. "The prime finder program rigorously tests all elements of a system -- from the logic of the processors, to the memory, the compiler and the operating and multitasking systems. For high performance systems with multiple processors, this is an excellent test of the system's ability to keep track of where all the data is."

Slowinski said the recent CRAY T94 system test in which the new prime number was discovered ran for over 6 hours on one central processing unit of the system. "If a machine can complete this exhaustive run-through, we can be confident everything is working as it should," said Slowinski.

In addition, Slowinski said, techniques used to speed up the performance of the prime finder can also be used to enhance the performance of programs customers use on real-world problems such as forecasting the weather and searching for oil.

"Through our work on the prime finder program, we learn new techniques for speeding up certain kinds of mathematical operations. These operations are often key elements of the most computation-intensive portions of software programs our customers run routinely on their Cray systems," said Slowinski.

With Prime Comes Perfect

[The new perfect number is 2^1257786*(2^1257787-1) which has 757,263 digits]

Slowinski noted that with the discovery of the new prime number, a new "perfect" number can also be generated. A perfect number is equal to the sum of its factors. For example, 6 is perfect because its factors -- 1, 2 and 3 -- when added together, equal 6. Mathematicians don't know how many perfect numbers exist. They do know, however, that all [even] perfect numbers have a direct relationship to Mersenne primes.

Cray Research, a wholly owned subsidiary of Silicon Graphics, Inc., provides the leading supercomputing tools and services to help solve customers' most challenging problems.

Mardi Larson
Media Relations Manager
Corporate Communications
Cray Research, Inc.

Printed from the PrimePages <t5k.org> © Reginald McLean.