The twentyfourth Fermat number is composite
Authors:
Richard E. Crandall, Ernst W. Mayer and Jason S. Papadopoulos
Journal:
Math. Comp. 72 (2003), 15551572
MSC (2000):
Primary 11Y11, 11Y16, 68Q25, 11A51
Published electronically:
December 6, 2002
MathSciNet review:
1972753
Fulltext 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 floatingpoint, FFTbased 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 floatingpoint runs, a separate algorithm for pureinteger 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 SelfridgeHurwitz 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), 217224. 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
(93k:11014), http://dx.doi.org/10.1090/S00255718199311975115
 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
(93a:11106), http://dx.doi.org/10.1090/S00255718199211347174
 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,
SpringerVerlag, New York; TELOS. The Electronic Library of Science, Santa
Clara, CA, 1996. MR 1392472
(97g:65005)
 9.
R.
Crandall, J.
Doenias, C.
Norrie, and J.
Young, The twentysecond Fermat number is
composite, Math. Comp. 64
(1995), no. 210, 863–868. MR 1277765
(95f:11104), http://dx.doi.org/10.1090/S00255718199512777659
 10.
Richard
Crandall and Barry
Fagin, Discrete weighted transforms and
largeinteger arithmetic, Math. Comp.
62 (1994), no. 205, 305–324. MR 1185244
(94c:11123), http://dx.doi.org/10.1090/S00255718199411852441
 11.
R. Crandall, ``Parallelization of Pollardrho factorization," manuscript, http://www.perfsci.com, (1999).
 12.
Richard
Crandall and Carl
Pomerance, Prime numbers, SpringerVerlag, New York, 2001. A
computational perspective. MR 1821158
(2002a:11007)
 13.
William
Feller, An introduction to probability theory and its applications.
Vol. I, Third edition, John Wiley & Sons, Inc., New
YorkLondonSydney, 1968. MR 0228020
(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 FloatingPoint Arithmetic, ANSI/IEEE Standard 7541985, IEEE (1985).
 19.
W. Keller, Fermatnumber 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 opensource 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), 5259. (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,
SpringerVerlag, BerlinNew York, 1981. MR 606376
(83e:65219)
 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
(95h:11142)
 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
(45 #1431)
 28.
J.
L. Selfridge and Alexander
Hurwitz, Fermat numbers and Mersenne
numbers, Math. Comp. 18 (1964), 146–148. MR 0159775
(28 #2991), http://dx.doi.org/10.1090/S00255718196401597758
 29.
V. Trevisan and J. B. Carvalho, "The composite character of the twentysecond Fermat number," J. Supercomputing 9 (1995), 179182.
 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
(89b:11012), http://dx.doi.org/10.1090/S00255718198809178338
 32.
P. Zimmerman, private communication (2001).
 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), 217224. 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, 151153, (1993). MR 93k:11014
 5.
 J. Buhler, R. Crandall, R. W. Sompolski, ``Irregular Primes to One Million,'' Math. Comp. 59, 717722 (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).^{}
 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 TwentySecond Fermat Number is Composite," Math. Comp. 64 (1995), 863868. MR 95f:11104
 10.
 R. Crandall and B. Fagin, ``Discrete Weighted Transforms and LargeInteger Arithmetic," Math. Comp. 62 (1994), 305324. MR 94c:11123
 11.
 R. Crandall, ``Parallelization of Pollardrho 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 FloatingPoint Arithmetic, ANSI/IEEE Standard 7541985, IEEE (1985).
 19.
 W. Keller, Fermatnumber 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 opensource 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), 5259. (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) 282292. MR 45:1431
 28.
 J. L. Selfridge and A. Hurwitz, ``Fermat numbers and Mersenne numbers," Math. Comp. 18 (1964), 146148. MR 28:2991
 29.
 V. Trevisan and J. B. Carvalho, "The composite character of the twentysecond Fermat number," J. Supercomputing 9 (1995), 179182.
 30.
 G. Woltman, private communication (1999).
 31.
 J. Young amd D. Buell, ``The Twentieth Fermat Number is Composite," Math. Comp. 50 (1988), 261263. 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:
http://dx.doi.org/10.1090/S0025571802014795
PII:
S 00255718(02)014795
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
