The twenty-fourth Fermat number is composite
HTML articles powered by AMS MathViewer
- by Richard E. Crandall, Ernst W. Mayer and Jason S. Papadopoulos PDF
- Math. Comp. 72 (2003), 1555-1572 Request permission
Abstract:
We have shown by machine proof that $F_{24} = 2^{2^{24}} + 1$ 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 $F_{24}$. 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 $F_{24}$ 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 $F_{23}$, and via the Suyama test determined that the known cofactor of this number is composite.References
- 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.
- M. Ashworth and A. G. Lyne, “A Segmented FFT Algorithm for Vector Computers,” Parallel Computing 6 (1988), 217-224.
- D. Bailey, “FFTs in External or Hierarchical Memory," (1989) manuscript.
- 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, DOI 10.1090/S0025-5718-1993-1197511-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, DOI 10.1090/S0025-5718-1992-1134717-4
- S. Losinsky, Sur le procédé d’interpolation de Fejér, C. R. (Doklady) Acad. Sci. URSS (N.S.) 24 (1939), 318–321 (French). MR 0002001
- C. Burrus, DFT/FFT and Convolution Algorithms: Theory and Implementation, Wiley, New York, 1985.
- Richard E. Crandall, Topics in advanced scientific computation, Springer-Verlag, New York; TELOS. The Electronic Library of Science, Santa Clara, CA, 1996. MR 1392472, DOI 10.1007/978-1-4612-2334-4
- 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, DOI 10.1090/S0025-5718-1995-1277765-9
- Richard Crandall and Barry Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994), no. 205, 305–324. MR 1185244, DOI 10.1090/S0025-5718-1994-1185244-1
- R. Crandall, “Parallelization of Pollard-rho factorization," manuscript, http://www.perfsci.com, (1999).
- Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158, DOI 10.1007/978-1-4684-9316-0
- William Feller, An introduction to probability theory and its applications. Vol. I, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020
- M. Frigo and S. Johnson, “The fastest Fourier transform in the west," http://theory.lcs.mit.edu/fftw.
- E. W. Mayer, GIMPS Source Code Timings Page, http://hogranch.com/mayer/gimps_timings.html#accuracy.
- G. B. Valor, private communication (2001).
- GIMPS homepage, http://www.mersenne.org.
- IEEE Standard for Binary Floating-Point Arithmetic, ANSI/IEEE Standard 754-1985, IEEE (1985).
- W. Keller, Fermat-number website data: http://www.prothsearch.net/fermat.html.
- W. Keller, private communication (1999).
- H. Lenstra, private communication (1999).
- E. Mayer, Mlucas: an open-source program for testing the character of Mersenne numbers. http://hogranch.com/mayer/README.html.
- 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.)
- Henri J. Nussbaumer, Fast Fourier transform and convolution algorithms, Springer Series in Information Sciences, vol. 2, Springer-Verlag, Berlin-New York, 1981. MR 606376
- C. Percival, PiHex: A distributed effort to calculate Pi. http://www.cecm.sfu.ca/projects/pihex/index.html.
- 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, DOI 10.1007/978-1-4612-0251-6
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
- J. L. Selfridge and Alexander Hurwitz, Fermat numbers and Mersenne numbers, Math. Comp. 18 (1964), 146–148. MR 159775, DOI 10.1090/S0025-5718-1964-0159775-8
- V. Trevisan and J. B. Carvalho, "The composite character of the twenty-second Fermat number," J. Supercomputing 9 (1995), 179-182.
- G. Woltman, private communication (1999).
- Jeff Young and Duncan A. Buell, The twentieth Fermat number is composite, Math. Comp. 50 (1988), no. 181, 261–263. MR 917833, DOI 10.1090/S0025-5718-1988-0917833-8
- P. Zimmerman, private communication (2001).
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
- Received by editor(s): October 14, 1999
- Received by editor(s) in revised form: September 5, 2001
- Published electronically: December 6, 2002
- © Copyright 2002 American Mathematical Society
- Journal: Math. Comp. 72 (2003), 1555-1572
- MSC (2000): Primary 11Y11, 11Y16, 68Q25, 11A51
- DOI: https://doi.org/10.1090/S0025-5718-02-01479-5
- MathSciNet review: 1972753