|
The twenty-fourth Fermat number is composite
Author(s):
Richard
E.
Crandall;
Ernst
W.
Mayer;
Jason
S.
Papadopoulos.
Journal:
Math. Comp.
72
(2003),
1555-1572.
MSC (2000):
Primary 11Y11, 11Y16, 68Q25, 11A51
Posted:
December 6, 2002
Retrieve article in:
PDF
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.
References:
-
- 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).
- 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:
10.1090/S0025-5718-02-01479-5
PII:
S 0025-5718(02)01479-5
Received by editor(s):
October 14, 1999
Received by editor(s) in revised form:
September 5, 2001
Posted:
December 6, 2002
Copyright of article:
Copyright
2002,
American Mathematical Society
|