Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Factorization of the tenth Fermat number


Author: Richard P. Brent
Journal: Math. Comp. 68 (1999), 429-451
MSC (1991): Primary 11Y05, 11B83, 11Y55; Secondary 11--04, 11A51, 11Y11, 11Y16, 14H52, 65Y10, 68Q25
DOI: https://doi.org/10.1090/S0025-5718-99-00992-8
MathSciNet review: 1489968
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We describe the complete factorization of the tenth Fermat number $F_{10}$ by the elliptic curve method (ECM). $F_{10}$ is a product of four prime factors with 8, 10, 40 and 252 decimal digits. The 40-digit factor was found after about 140 Mflop-years of computation. We also discuss the complete factorization of other Fermat numbers by ECM, and summarize the factorizations of $F_5, \dots, F_{11}$.


References [Enhancements On Off] (What's this?)

  • 1. A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29-68. Programs available from ftp://ftp.inria.fr/
    [0]INRIA/ecpp.V3.4.1.tar.Z
    . MR 93m:11136
  • 2. D. J. Bernstein, Detecting perfect powers in essentially linear time, Math. Comp., to appear. Available from ftp://koobera.math.uic.edu/
    [0]pub/
    [0]papers/
    [0]powers.dvi
    . CMP 97:16
  • 3. H. Boender and H. J. J. te Riele, Factoring integers with large prime variations of the quadratic sieve, Experimental Mathematics, 5 (1996), 257-273. Also Report NM-R9513, Department of Numerical Mathematics, Centrum voor Wiskunde en Informatica, Amsterdam, July 1995. ftp://ftp.cwi.nl/
    [0]pub/CWIreports/NW/
    [0]NM-R9513.ps.Z
    MR 97m:11155
  • 4. W. Bosma and A. K. Lenstra, An implementation of the elliptic curve integer factorization method, Computational Algebra and Number Theory (edited by W. Bosma and A. van der Poorten), Kluwer Academic Publishers, Dordrecht, 1995, 119-136. MR 96d:11134
  • 5. R. P. Brent, Algorithm 524: MP, a Fortran multiple-precision arithmetic package, ACM Trans. on Mathematical Software 4 (1978), 71-81.
  • 6. R. P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), 176-184. MR 82a:10007
  • 7. R. P. Brent, Succinct proofs of primality for the factors of some Fermat numbers, Math. Comp. 38 (1982), 253-255. MR 82k:10002
  • 8. R. P. Brent, Some integer factorization algorithms using elliptic curves, Australian Computer Science Communications 8 (1986), 149-163. Also Report CMA-R32-85, Centre for Mathematical Analysis, Australian National University, Canberra, Sept. 1985, 20 pp.
  • 9. R. P. Brent, Factorization of the eleventh Fermat number (preliminary report), AMS Abstracts 10 (1989), 89T-11-73.
  • 10. R. P. Brent, Factor: an integer factorization program for the IBM PC, Report TR-CS-89-23, Computer Sciences Laboratory, Australian National Univ., Canberra, Oct. 1989, 7 pp.
  • 11. R. P. Brent, Parallel algorithms for integer factorisation, Number Theory and Cryptography (edited by J. H. Loxton), Cambridge University Press, 1990. MR 91h:11145
  • 12. R. P. Brent, On computing factors of cyclotomic polynomials, Math. Comp. 61 (1993), 131-149. MR 92m:11131
  • 13. R. P. Brent, Factorization of the tenth and eleventh Fermat numbers, Report TR-CS-96-02, Computer Sciences Laboratory, Australian National Univ., Canberra, Feb. 1996. ftp://nimbus.anu.edu.au/
    [0]pub/Brent/rpb161tr.dvi.gz
    .
  • 14. R. P. Brent, Large factors found by ECM, Computer Sciences Laboratory, Australian National University, Dec. 1995 (and more recent updates). ftp://nimbus.anu.edu.au/
    [0]pub/
    [0]Brent/
    [0]champs.ecm
    .
  • 15. R. P. Brent, Primality certificates for factors of some Fermat numbers, Computer Sciences Laboratory, Australian National University, Nov. 1995. ftp://nimbus.anu.edu.au/
    [0]pub/Brent/F10p252.cer, F11p564.cer
    .
  • 16. R. P. Brent, G. L. Cohen and H. J. J. te Riele, Improved techniques for lower bounds for odd perfect numbers, Math. Comp. 57 (1991), 857-868. MR 92c:11004
  • 17. R. P. Brent, R. E. Crandall and K. Dilcher, Two new factors of Fermat numbers, Report TR-CS-97-11, Australian National University, May 1997, 7 pp. ftp://nimbus.anu.edu.au/
    [0]pub/Brent/rpb175tr.dvi.gz
    .
  • 18. R. P. Brent and J. M. Pollard, Factorization of the eighth Fermat number, Math. Comp. 36 (1981), 627-630. MR 83h:10014
  • 19. R. P. Brent and H. J. J. te Riele, Factorizations of $a^n \pm 1$, $13 \le a < 100$, Report NM-R9212, Department of Numerical Mathematics, Centrum voor Wiskunde en Informatica, Amsterdam, June 1992. Also (with P. L. Montgomery), updates to the above. ftp://nimbus.anu.edu.au/
    [0]pub/Brent/rpb134*.*.gz
    .
  • 20. J. Brillhart, Some miscellaneous factorizations, Math. Comp. 17 (1963), 447-450.
  • 21. J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of $b^n \pm 1$, $b = 2, 3, 5, 6, 7, 10, 11, 12$ up to high powers, 2nd ed., Amer. Math. Soc., Providence, RI, 1988. Also updates to Update 2.9, August 16, 1995. MR 90d:11009
  • 22. N. G. de Bruijn, The asymptotic behaviour of a function occurring in the theory of primes, J. Indian Math. Soc. 15 (1951), 25-32. MR 13:362f
  • 23. D. V. and G. V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Adv. in Appl. Math. 7 (1986), 385-434. MR 88h:11094
  • 24. H. Cohen, Elliptic curves, From Number Theory to Physics (edited by M. Waldschmidt, P. Moussa, J.-M. Luck and C. Itzykson), Springer-Verlag, New York, 1992, 212-237. MR 94e:11063
  • 25. R. E. Crandall, Projects in scientific computation, Springer-Verlag, New York, 1994. MR 95d:65001
  • 26. R. E. Crandall, Topics in advanced scientific computation, Springer-Verlag, New York, 1996. MR 97g:65005
  • 27. 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
  • 28. R. Crandall and B. Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994), 305-324. MR 94c:11123
  • 29. A. J. C. Cunningham and H. J. Woodall, Factorisation of $y^n \mp 1$, $y = 2, 3, 5, 6, 7, 10, 11, 12$ up to high powers (n), Hodgson, London, 1925.
  • 30. K. Dickman, On the frequency of numbers containing prime factors of a certain relative magnitude, Ark. Mat., Astronomi och Fysik 22A, 10 (1930), 1-14.
  • 31. B. Dixon and A. K. Lenstra, Massively parallel elliptic curve factoring, Proc. Eurocrypt '92, Lecture Notes in Computer Science 658, Springer-Verlag, Berlin, 1993, 183-193.
  • 32. M. Elkenbracht-Huizing, An implementation of the number field sieve, Experimental Mathematics, 5 (1996), 231-253. MR 98a:11182
  • 33. V. Goncharov, On the field of combinatory analysis, Izv. Akad. Nauk SSSR Ser. Mat. 8 (1944), 3-48; English transl. in Amer. Math. Soc. Transl. (2) 19 (1962), 1-46.
  • 34. G. B. Gostin, New factors of Fermat numbers, Math. Comp. 64 (1995), 393-395. MR 95c:11151
  • 35. J. C. Hallyburton and H. Brillhart, Two new factors of Fermat numbers, Math. Comp. 29 (1975), 109-112. Corrigendum, ibid 30 (1976), 198. MR 51:5460; MR 52:13599
  • 36. W. Keller, Factors of Fermat numbers and large primes of the form $k \cdot 2^n + 1$, Math. Comp. 41 (1983), 661-673. Also part II, preprint, Universität Hamburg, Sept. 27, 1992 (available from the author). MR 85b:11117
  • 37. W. Keller, New Cullen primes, Math. Comp. 64 (1995), 1733-1741. MR 95m:11015
  • 38. D. E. Knuth, The art of computer programming, Volume 2: Seminumerical algorithms (2nd ed.), Addison-Wesley, Menlo Park, CA, 1981. MR 44:3531
  • 39. D. E. Knuth and L. Trabb Pardo, Analysis of a simple factorization algorithm, Theor. Comp. Sci. 3 (1976), 321-348. MR 58:16485
  • 40. M. Kraitchik, Théorie des nombres, Tome 2, Gauthier-Villars, Paris, 1926.
  • 41. F. Landry, Note sur la décomposition du nombre $2^{64} + 1$ (Extrait), C. R. Acad. Sci. Paris 91 (1880), 138.
  • 42. D. H. Lehmer, Tests for primality by the converse of Fermat's theorem, Bull Amer. Math. Soc. 33 (1927), 327-340.
  • 43. A. K. Lenstra and H. W. Lenstra, Jr. (editors), The development of the number field sieve, Lecture Notes in Mathematics 1554, Springer-Verlag, Berlin, 1993. MR 96m:11116
  • 44. A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The factorization of the ninth Fermat number, Math. Comp. 61 (1993), 319-349. MR 93k:11116
  • 45. A. K. Lenstra and M. S. Manasse, Factoring by electronic mail, Proc. Eurocrypt '89, Lecture Notes in Computer Science 434, Springer-Verlag, Berlin, 1990, 355-371. MR 91i:11182
  • 46. H. W. Lenstra, Jr., Factoring integers with elliptic curves, Annals of Mathematics (2) 126 (1987), 649-673. MR 89g:11125
  • 47. E. Lucas, Théorie des fonctions numériques simplement periodiques, Amer. J. Math. 1 (1878), 184-239 & 289-321.
  • 48. J. van de Lune and E. Wattel, On the numerical solution of a differential-difference equation arising in analytic number theory, Math. Comp. 23 (1969), 417-421. MR 40:1050
  • 49. J. F. McKee, Subtleties in the distribution of the numbers of points on elliptic curves over a finite prime field, J. London Math. Soc., to appear.
  • 50. P. L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), 243-264. MR 88e:11130
  • 51. P. L. Montgomery, An FFT extension of the elliptic curve method of factorization, Ph. D. dissertation, Mathematics, University of California at Los Angeles, 1992. ftp://ftp.cwi.nl/
    [0]pub/
    [0]pmontgom/
    [0]ucladissertation.
    [0]psl.Z
    .
  • 52. P. L. Montgomery, A survey of modern integer factorization algorithms, CWI Quarterly 7 (1994), 337-366. MR 96b:11161
  • 53. P. L. Montgomery, personal communication by e-mail, November 29, 1995.
  • 54. F. Morain, Courbes elliptiques et tests de primalité, Ph. D. thesis, Univ. Claude Bernard - Lyon I, France, 1990. ftp://ftp.inria.fr/
    [0]INRIA/
    [0]publication/
    [0]Theses/
    [0]TU-0144.tar.Z
    . MR 95i:11149
  • 55. M. A. Morrison and J. Brillhart, A method of factorization and the factorization of $F_7$, Math. Comp. 29 (1975), 183-205. MR 51:8017
  • 56. M. Paterson and L. Stockmeyer, On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. on Computing 2 (1973), 60-66. MR 47:2790
  • 57. J. M. Pollard, Theorems in factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521-528. MR 50:6992
  • 58. J. M. Pollard, A Monte Carlo method for factorization, BIT 15 (1975), 331-334. MR 52:13611
  • 59. C. Pomerance, The quadratic sieve factoring algorithm, Advances in Cryptology, Proc. Eurocrypt '84, Lecture Notes in Computer Science, Vol. 209, Springer-Verlag, Berlin, 1985, 169-182. MR 87d:11098
  • 60. C. Pomerance, The number field sieve, Proceedings of Symposia in Applied Mathematics 48, Amer. Math. Soc., Providence, Rhode Island, 1994, 465-480. MR 96c:11143
  • 61. C. Pomerance, A tale of two sieves, Notices Amer. Math. Soc. 43 (1996), 1473-1485. MR 97f:11100
  • 62. H. Riesel, Prime numbers and computer methods for factorization, 2nd edition, Birkhäuser, Boston, 1994. MR 95h:11142
  • 63. R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), 120-126. MR 83m:94003
  • 64. R. M. Robinson, Mersenne and Fermat numbers, Proc. Amer. Math. Soc. 5 (1954), 842-846. MR 16:335d
  • 65. J. L. Selfridge, Factors of Fermat numbers, MTAC 7 (1953), 274-275.
  • 66. D. Shanks, Class number, a theory of factorization, and genera, Proc. Symp. Pure Math. 20, American Math. Soc., Providence, R. I., 1971, 415-440. MR 47:4932
  • 67. L. A. Shepp and S. P. Lloyd, Ordered cycle lengths in a random permutation, Trans. Amer. Math. Soc. 121 (1966), 340-357. MR 33:3320
  • 68. P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proc. 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, California, 1994, 124. CMP 98:06
  • 69. J. H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics 106, Springer-Verlag, New York, 1986. MR 87g:11070
  • 70. R. D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), 329-339. MR 88c:11079
  • 71. R. D. Silverman and S. S. Wagstaff, Jr., A practical analysis of the elliptic curve factoring algorithm, Math. Comp. 61 (1993), 445-462. MR 93k:11117
  • 72. H. Suyama, Informal preliminary report (8), personal communication, October 1985.
  • 73. A. M. Vershik, The asymptotic distribution of factorizations of natural numbers into prime divisors, Dokl. Akad. Nauk SSSR 289 (1986), 269-272; English transl. in Soviet Math. Dokl. 34 (1987), 57-61. MR 87i:11115
  • 74. H. C. Williams, How was $F_6$ factored?, Math. Comp. 61 (1993), 463-474. MR 93k:01046
  • 75. H. C. Williams and J. S. Judd, Some algorithms for prime testing using generalized Lehmer functions, Math. Comp. 30 (1976), 867-886. MR 54:2574

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y05, 11B83, 11Y55, 11--04, 11A51, 11Y11, 11Y16, 14H52, 65Y10, 68Q25

Retrieve articles in all journals with MSC (1991): 11Y05, 11B83, 11Y55, 11--04, 11A51, 11Y11, 11Y16, 14H52, 65Y10, 68Q25


Additional Information

Richard P. Brent
Affiliation: Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford, OX1 3QD, United Kingdom

DOI: https://doi.org/10.1090/S0025-5718-99-00992-8
Keywords: Computational number theory, Cunningham project, ECM, elliptic curve method, factorization, Fermat number, $F_9$, $F_{10}$, $F_{11}$, integer factorization
Received by editor(s): February 2, 1996
Received by editor(s) in revised form: May 20, 1997
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society