Mathematics of Computation

Author(s): 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
Retrieve article in: PDF
This article is available free of charge

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}$ .

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$ , 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$ , 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 , 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 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

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

DOI: 10.1090/S0025-5718-99-00992-8
PII: S 0025-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
Copyright of article: Copyright 1999, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS