Steve Conway, 612/683-7133
LARGEST KNOWN PRIME NUMBER DISCOVERED ON CRAY
RESEARCH SUPERCOMPUTER
EAGAN, Minn., Jan. 10, 1994 -- Computer scientists at Cray
Research, Inc. have discovered the largest-known prime
number while conducting tests on a CRAY C90 series
supercomputer.
The new prime number has 258,716 digits. Printed in
newspaper-sized type, the number would fill approximately 8
newspaper pages.
In mathematical notation, the new prime number is expressed
as 2^859433-1, which denotes two, multiplied by itself
859,433 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.
The largest Mersenne prime known previously was discovered
in February 1992 at AEA Technology's Harwell Laboratory in
England by computer scientists who were also conducting a
test of a Cray Research supercomputer. It had 227,832 digits.
Six of the last seven Mersenne primes were discovered on Cray
Research supercomputers.
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 formula for generating them.
Therefore, the discovery of new primes requires randomly
generating and testing millions of numbers.
"Finding these special numbers is a true 'needle-in-a-haystack'
exercise, but we improve our odds by using a tremendously
fast computer 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., independently verified that the number
Slowinski and Gage found is prime and will note the discovery
in a textbook to be published shortly.
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 C90 test in which the new prime number was discovered
would run for over 7 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 on their systems," said Slowinski.
Slowinski compared running the prime finder on
supercomputers and continually "tuning" the program to
building and racing exotic cars. "There aren't many practical
uses for dragsters or Formula 1 race cars. But some things
engineers do to make those cars perform better eventually find
their way into cars you and I drive," said Slowinski.
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
perfect numbers have a direct relationship to Mersenne primes.
The new perfect number generated with the new Mersenne
prime is the 33rd known perfect number and has 517,430
digits. The 32nd perfect number had 455,663 digits.
Cray Research creates the most powerful, highest quality
computational tools for solving the world's most challenging
scientific and industrial problems.
###