Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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
DOI: https://doi.org/10.1090/S0025-5718-02-01479-5
Published electronically: December 6, 2002
MathSciNet review: 1972753
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 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, T. Metsankyla, ``Irregular Primes to Four Million,'' Math. Comp. 61, 151-153, (1993). MR 93k:11014
  • 5. J. Buhler, R. Crandall, R. W. Sompolski, ``Irregular Primes to One Million,'' Math. Comp. 59, 717-722 (1992). MR 93a:11106
  • 6. J. Buhler, R. Crandall, R. Ernvall, T. Metsankyla, A. Shokrollahi, ``Irregular Primes and Cyclotomic Invariants to Eight Million,'' manuscript (1996).% latex2html id marker 197 \setcounter{footnote}{1}\fnsymbol{footnote}
  • 7. C. Burrus, DFT/FFT and Convolution Algorithms: Theory and Implementation, Wiley, New York, 1985.
  • 8. R. E. Crandall, Topics in Advanced Scientific Computation, Springer, New York, 1996. MR 97g:65005
  • 9. R. Crandall, J. Doenias, C. Norrie, and J. Young, ``The Twenty-Second Fermat Number is Composite," Math. Comp. 64 (1995), 863-868. MR 95f:11104
  • 10. R. Crandall and B. Fagin, ``Discrete Weighted Transforms and Large-Integer Arithmetic," Math. Comp. 62 (1994), 305-324. MR 94c:11123
  • 11. R. Crandall, ``Parallelization of Pollard-rho factorization," manuscript, http://www.perfsci.com, (1999).
  • 12. R. Crandall and C. Pomerance, Prime numbers: a computational perspective, Springer, New York, (2001) MR 2002a:11007
  • 13. W. Feller, ``An Introduction to Probability Theory and Its Applications," Vol. I, 3rd ed., Wiley, New York, 1968. MR 37:3604
  • 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. H. J. Nussbaumer, Fast Fourier Transform and Convolution Algorithms, 2nd ed., Volume 2 of Springer Series in Information Sciences, Springer, New York, 1982. MR 83e:65219
  • 25. C. Percival, PiHex: A distributed effort to calculate Pi. http://www.cecm.sfu.ca/projects/pihex/index.html.
  • 26. H. Riesel, Prime Numbers and Computer Methods for Factorization, 2nd ed., Birkhäuser, Boston, 1994. MR 95h:11142
  • 27. A. Schönhage 1971, Schnelle Multiplikation grosser Zahlen, Computing 7 (1971) 282-292. MR 45:1431
  • 28. J. L. Selfridge and A. Hurwitz, ``Fermat numbers and Mersenne numbers," Math. Comp. 18 (1964), 146-148. MR 28:2991
  • 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. J. Young amd D. Buell, ``The Twentieth Fermat Number is Composite," Math. Comp. 50 (1988), 261-263. MR 89b:11012
  • 32. P. Zimmerman, private communication (2001).

Similar Articles

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: https://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

American Mathematical Society