TECHNICAL NEWS RELEASE (29 Sep 1999)
DEEPEST COMPUTATION IN HISTORY, FOR A YES/NO ANSWER
Contact:
Dr. Richard Crandall
Director
Center for Advanced Computation
Reed College, Portland Oregon
(503) 777-7255
email: [EMAIL PROTECTED]
What is believed to be the deepest computation -- for a simple "yes/no" or
"1-bit" answer -- in history has just been completed by a team of three
investigators: Ernst Mayer, formerly of Case Western Reserve University,
Cleveland, Ohio; Jason Papadopoulos of the University of Maryland, College
Park, Maryland; and Richard Crandall of the Center for Advanced Computation,
Reed College, Portland, Oregon.
The computation involves a gargantuan, mysterious number
called F24, the twenty-fourth Fermat number. F24 is over 5 million decimal
digits in length, and the three investigators have answered the question: "is
F24 a prime number?". The answer, based on their intensive computation, is
"no." This means that there must exist proper factors of F24, though not a
single explicit factor is yet known. (See end of article for background on
the
celebrated Fermat numbers.)
Mayer and Papadopoulos used independent, floating-point
"wavefront" implementations of the rigorous, classical Pepin primality proof;
which runs were completed on 27 and 31 Aug 1999 respectively, ending up in
complete agreement on the final Pepin residue, said residue not equal to (-1)
as required for primality. During these "wavefront" runs Crandall used a
pure-integer convolution scheme in parallel mode (i.e. running on many
computers simultaneously), to check the periodically deposited wavefront
residues. With this integer verification, the proof is considered rigorous:
there is no doubt that F24 is composite.
The mathematical details will be published later (a preprint of the three
authors' paper is available at www.perfsci.com/free/techpapers). Many
colleagues of the three investigators contributed to this massive
computational project (see below for detailed acknowledgements).
F24 = 2^(2^24) + 1 at over 5 million digits dwarfs the current largest known
prime 2^6972593-1, which is a "mere" 2 million digits (see www.mersenne.org,
www.perfsci.com, www.entropia.com).
To convey the scale of the computation, consider that the Pixar-Disney movie
"A Bug's Life" needed about 10^17 (one hundred quadrillion) computer
operations
for its complete rendering, yet essentially the same number of operations went
into the F24 proof. So the amusing notion is: for 10^17 operations you can
either get a feature-length state-of-the-art synthetic movie, or for similar
computational cost you can get a 1-bit answer (prime/not prime).
Fermat numbers are numbers of the form Fn = 2^(2^n) + 1. Written in binary
the n-th Fermat number consists of a binary one, followed by 2^n zeros and a
trailing one. For example, in binary F2 = 11 and F4 = 11.
Each time you increase the index n by one, the number of binary zeros, and
thus the number of digits (in either binary or decimal form) also roughly
doubles. P. Fermat conjectured in the early 1600's that each of the Fn is
prime. He had in hand the first five examples F0 = 3, F1 = 5, F2 = 17, F3 =
257 and F4 = 65537, each of which being indeed prime. However, unlike his
celebrated "last theorem" recently proved by A. Wiles, Fermat's conjecture
regarding the primality of the Fn turns out to be about as wrong as can be.
Not
a single prime Fermat number is known beyond F4. For example, F5 =
4294967297
is divisible by 641, and every other Fermat number has either exhibited
factors, or remains of unknown character (prime/composite).
When factoring algorithms fail to produce an explicit factor, the Fermat
number in question can still be subjected to a Pepin test, a deterministic
test
of primality. This test requires a sequence of squarings of numbers, a member
of the sequence being generally as large as the Fermat number under test,
and one must do as many such squarings as there are binary zeros in the
Fermat number in question. The primality test for F24 thus requires
16777215 squarings, each such squaring being of a number over five
million decimal digits in length. Even though it is now generally believed
that are no more prime Fermat numbers beyond those found by Fermat himself,
the testing of these numbers has proved to be a valuable exercise, since each
new test tends to occur, for the given era, at the edge of feasibility on
state-of-art computer hardware, not to mention at the fringe of algorithm
development.
There have also been important theoretical and algorithmic advances spurred by
such work, and many of the fundamental algorithms used for the Fermat numbers
are also widely used in other areas - for example, the two floating-point
Pepin tests of F24 each used an efficient squaring algorithm based on a
procedure called the fast Fourier transform (FFT), which is ubiquitous in the
field of
