The twenty-fourth Fermat number is composite

Authors:
Richard E. Crandall, Ernst W. Mayer and Jason S. Papadopoulos

Journal:
Math. Comp. **72** (2003), 1555-1572

MSC (2000):
Primary 11Y11, 11Y16, 68Q25, 11A51

Published electronically:
December 6, 2002

MathSciNet review:
1972753

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We have shown by machine proof that is composite. The rigorous Pépin primality test was performed using independently developed programs running simultaneously on two different, physically separated processors. Each program employed a floating-point, FFT-based discrete weighted transform (DWT) to effect multiplication modulo . The final, respective Pépin residues obtained by these two machines were in complete agreement. Using intermediate residues stored periodically during one of the floating-point runs, a separate algorithm for pure-integer negacyclic convolution verified the result in a ``wavefront'' paradigm, by running simultaneously on numerous additional machines, to effect piecewise verification of a saturating set of deterministic links for the Pépin chain. We deposited a final Pépin residue for possible use by future investigators in the event that a proper factor of should be discovered; herein we report the more compact, traditional Selfridge-Hurwitz residues. For the sake of completeness, we also generated a Pépin residue for , and via the Suyama test determined that the known cofactor of this number is composite.

**1.**R. C. Agarwal and J. W. Cooley,``Fourier Transform and Convolution Subroutines for the IBM 3090 Vector Facility,''*IBM Journal of Research and Development***30**(1986), 145 - 162. CMP**18:12****2.**M. Ashworth and A. G. Lyne, ``A Segmented FFT Algorithm for Vector Computers,''*Parallel Computing***6**(1988), 217-224. CMP**20:07****3.**D. Bailey, ``FFTs in External or Hierarchical Memory," (1989) manuscript.**4.**J. Buhler, R. Crandall, R. Ernvall, and T. Metsänkylä,*Irregular primes and cyclotomic invariants to four million*, Math. Comp.**61**(1993), no. 203, 151–153. MR**1197511**, 10.1090/S0025-5718-1993-1197511-5**5.**J. P. Buhler, R. E. Crandall, and R. W. Sompolski,*Irregular primes to one million*, Math. Comp.**59**(1992), no. 200, 717–722. MR**1134717**, 10.1090/S0025-5718-1992-1134717-4**6.**J. Buhler, R. Crandall, R. Ernvall, T. Metsankyla, A. Shokrollahi, ``Irregular Primes and Cyclotomic Invariants to Eight Million,'' manuscript (1996).^{}**7.**C. Burrus,*DFT/FFT and Convolution Algorithms: Theory and Implementation*, Wiley, New York, 1985.**8.**Richard E. Crandall,*Topics in advanced scientific computation*, Springer-Verlag, New York; TELOS. The Electronic Library of Science, Santa Clara, CA, 1996. MR**1392472****9.**R. Crandall, J. Doenias, C. Norrie, and J. Young,*The twenty-second Fermat number is composite*, Math. Comp.**64**(1995), no. 210, 863–868. MR**1277765**, 10.1090/S0025-5718-1995-1277765-9**10.**Richard Crandall and Barry Fagin,*Discrete weighted transforms and large-integer arithmetic*, Math. Comp.**62**(1994), no. 205, 305–324. MR**1185244**, 10.1090/S0025-5718-1994-1185244-1**11.**R. Crandall, ``Parallelization of Pollard-rho factorization," manuscript,`http://www.perfsci.com`, (1999).**12.**Richard Crandall and Carl Pomerance,*Prime numbers*, Springer-Verlag, New York, 2001. A computational perspective. MR**1821158****13.**William Feller,*An introduction to probability theory and its applications. Vol. I*, Third edition, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR**0228020****14.**M. Frigo and S. Johnson, ``The fastest Fourier transform in the west,"`http://theory.lcs.mit.edu/fftw`.**15.**E. W. Mayer, GIMPS Source Code Timings Page,`http://hogranch.com/mayer/gimps_timings.html#accuracy`.**16.**G. B. Valor, private communication (2001).**17.**GIMPS homepage,`http://www.mersenne.org`.**18.***IEEE Standard for Binary Floating-Point Arithmetic*, ANSI/IEEE Standard 754-1985, IEEE (1985).**19.**W. Keller, Fermat-number website data:`http://www.prothsearch.net/fermat.html`.**20.**W. Keller, private communication (1999).**21.**H. Lenstra, private communication (1999).**22.**E. Mayer, Mlucas: an open-source program for testing the character of Mersenne numbers.`http://hogranch.com/mayer/README.html`.**23.**R. R. Schaller,*Moore's law: past, present and future*,*IEEE Spectrum***34**(1997), 52-59. (Also cf.`http://www.intel.com/research/silicon/mooreslaw.htm`.)**24.**Henri J. Nussbaumer,*Fast Fourier transform and convolution algorithms*, Springer Series in Information Sciences, vol. 2, Springer-Verlag, Berlin-New York, 1981. MR**606376****25.**C. Percival, PiHex: A distributed effort to calculate Pi.`http://www.cecm.sfu.ca/projects/pihex/index.html`.**26.**Hans Riesel,*Prime numbers and computer methods for factorization*, 2nd ed., Progress in Mathematics, vol. 126, Birkhäuser Boston, Inc., Boston, MA, 1994. MR**1292250****27.**A. Schönhage and V. Strassen,*Schnelle Multiplikation grosser Zahlen*, Computing (Arch. Elektron. Rechnen)**7**(1971), 281–292 (German, with English summary). MR**0292344****28.**J. L. Selfridge and Alexander Hurwitz,*Fermat numbers and Mersenne numbers*, Math. Comp.**18**(1964), 146–148. MR**0159775**, 10.1090/S0025-5718-1964-0159775-8**29.**V. Trevisan and J. B. Carvalho, "The composite character of the twenty-second Fermat number,"*J. Supercomputing***9**(1995), 179-182.**30.**G. Woltman, private communication (1999).**31.**Jeff Young and Duncan A. Buell,*The twentieth Fermat number is composite*, Math. Comp.**50**(1988), no. 181, 261–263. MR**917833**, 10.1090/S0025-5718-1988-0917833-8**32.**P. Zimmerman, private communication (2001).

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11Y11,
11Y16,
68Q25,
11A51

Retrieve articles in all journals with MSC (2000): 11Y11, 11Y16, 68Q25, 11A51

Additional Information

**Richard E. Crandall**

Affiliation:
Center for Advanced Computation, Reed College, Portland, Oregon 97202

Email:
crandall@reed.edu

**Ernst W. Mayer**

Affiliation:
Department of Mech. & Aerospace Engineering, Case Western Reserve University, Cleveland, Ohio 44106

Address at time of publication:
10190 Parkwood Dr. Apt. 1, Cupertino, CA 95014

Email:
ewmayer@aol.com

**Jason S. Papadopoulos**

Affiliation:
Department of Elec. & Comp. Engineering, University of Maryland, College Park, Maryland 20742

Email:
jasonp@boo.net

DOI:
http://dx.doi.org/10.1090/S0025-5718-02-01479-5

Received by editor(s):
October 14, 1999

Received by editor(s) in revised form:
September 5, 2001

Published electronically:
December 6, 2002

Article copyright:
© Copyright 2002
American Mathematical Society