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 = 100001 and F4 = 100000000000000001. 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 electronic signal processing. The pure-integer convolution that verified the Pepin test also has wide application in arbitrary-precision arithmetic. In developing their separate implementations, each member of the team (Mayer, Papadopoulos, Crandall) made advances in the matter of implementation of the FFT and convolution algorithms on modern microprocessor architectures. We note that F22 was resolved (as composite) in 1993. Various Fermat numbers beyond F24 have been attributed at least one explicitly known small factor (see http://vamri.xray.ufl.edu/proths/fermat.html for the current computational knowledge pertaining to Fermat numbers), so that the next unresolved case is the monstrous F31 which (at over 600 million decimal digits), even with the aforementioned algorithmic advances, is out of reach with current technology. We estimate 10000 years processing on hardware of current vintage be required to resolve F31. However, history is replete with underestimates on future machinery and ingenuity. We are confident that with ever-faster processors and further algorithmic advances, in particular those aimed at implementation of the Pepin test on massively parallel computer hardware, a test of F31 may come within the next two decades. And this perhaps surprisingly optimistic estimate is made even without the benefit of quantum computers, nanotechnology, and so on; breakthroughs in any of these areas could alter the assailability of F31 dramatically. Background on investigators: Ernst W. Mayer was until recently on the faculty of Engineering of Case Western Reserve University in Cleveland, Ohio. He is currently working as a freelance computational number theorist and algorithm developer out of his home in Cupertino, Calfornia. Jason S. Papadopoulos is a graduate student in the Electrical Engineering school at the University of Maryland, College Park. His interests include cryptography, computational number theory, and high-performance scientific computing. Presently he works for 3S Group Inc, a Vienna, VA-based firm specializing in encryption hardware. Richard E. Crandall, author, lecturer and computationalist, is the Director of the Center for Advanced Computation, Reed College, holding also the title of Apple Distinguished Scientist. His algorithms have previously been used to resolve the character of F22, and to discover record primes such as the last several largest-known Mersenne primes. Acknowledgements: The three investigators gratefully acknowledge the theoretical and engineering contributions from J. Buhler, H. Lenstra, J. Klivington, C. Pomerance, J. Selfridge, P. Montgomery, G. Woltman. C. Curry, P. Wellin, R. Knapp, S. Wolfram. Alex Kruppa and the staff of the Infohalle der Fakultaet fuer Informatik an der Technischen Universitaet Muenchen lent considerable processing power and personal maintenance time to the integer proof runs. The first-completed floating- point run was performed on a Silicon Graphics R10000 Octane workstation - the investigators thank J. Alexander of Case Western Reserve University for his generous donation of machine time. Thanks are also due to 3S Group Incorporated for the extended use of a Sun UltraSPARC-1, used as the second floating-point machine. The Number Theory Foundation donated additional machinery for the final stages of the pure-integer proof, and a key segment of said proof was carried out on Apple Computer's newly announced G4 processor, which provides giga-op-level performance. A Reed College team of staff and students: N. Essy, B. Hanson, C. Chen, J. Dodson, R. Richter, W. Cooley, J. Heilman, D. Turner, (and from Univ. Georgia) C. Gunning finished in glorious and selfless fashion the last stages of the rigorous integer proof. For more information: Consult the algorithm website www.perfsci.com _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
