Factorization of the tenth Fermat number

Brent, Richard

doi:10.1090/S0025-5718-99-00992-8

Factorization of the tenth Fermat number
HTML articles powered by AMS MathViewer

by Richard P. Brent PDF

Math. Comp. 68 (1999), 429-451 Request permission

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

A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), no. 203, 29–68. MR 1199989, DOI 10.1090/S0025-5718-1993-1199989-X
D. J. Bernstein, Detecting perfect powers in essentially linear time, Math. Comp., to appear. Available from ftp://koobera.math.uic.edu/pub/papers/powers.dvi.
Henk Boender and Herman J. J. te Riele, Factoring integers with large-prime variations of the quadratic sieve, Experiment. Math. 5 (1996), no. 4, 257–273. MR 1437217, DOI 10.1080/10586458.1996.10504592
Wieb Bosma and Arjen K. Lenstra, An implementation of the elliptic curve integer factorization method, Computational algebra and number theory (Sydney, 1992) Math. Appl., vol. 325, Kluwer Acad. Publ., Dordrecht, 1995, pp. 119–136. MR 1344926
R. P. Brent, Algorithm 524: MP, a Fortran multiple-precision arithmetic package, ACM Trans. on Mathematical Software 4 (1978), 71–81.
Richard P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), no. 2, 176–184. MR 583032, DOI 10.1007/BF01933190
Richard P. Brent, Succinct proofs of primality for the factors of some Fermat numbers, Math. Comp. 38 (1982), no. 157, 253–255. MR 637304, DOI 10.1090/S0025-5718-1982-0637304-0
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.
R. P. Brent, Factorization of the eleventh Fermat number (preliminary report), AMS Abstracts 10 (1989), 89T-11-73.
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.
Alfred Wassermann, Konstruktion von Normalbasen, Bayreuth. Math. Schr. 31 (1990), 155–164 (German). MR 1056152
Richard Massy, Formules de construction de bases normales d’entiers relatives, C. R. Acad. Sci. Paris Sér. I Math. 313 (1991), no. 8, 477–482 (French, with English summary). MR 1131858
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/pub/Brent/rpb161tr.dvi.gz.
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/pub/Brent/champs.ecm.
R. P. Brent, Primality certificates for factors of some Fermat numbers, Computer Sciences Laboratory, Australian National University, Nov. 1995. ftp://nimbus.anu.edu.au/pub/Brent/F10p252.cer, F11p564.cer.
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), no. 196, 857–868. MR 1094940, DOI 10.1090/S0025-5718-1991-1094940-3
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/pub/Brent/rpb175tr.dvi.gz.
Richard P. Brent and John M. Pollard, Factorization of the eighth Fermat number, Math. Comp. 36 (1981), no. 154, 627–630. MR 606520, DOI 10.1090/S0025-5718-1981-0606520-5
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/pub/Brent/rpb134*.*.gz.
J. Brillhart, Some miscellaneous factorizations, Math. Comp. 17 (1963), 447–450.
John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^n \pm 1$, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. $b=2,3,5,6,7,10,11,12$ up to high powers. MR 996414, DOI 10.1090/conm/022
C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
D. V. Chudnovsky 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), no. 4, 385–434. MR 866702, DOI 10.1016/0196-8858(86)90023-0
Henri Cohen, Elliptic curves, From number theory to physics (Les Houches, 1989) Springer, Berlin, 1992, pp. 212–237. MR 1221102
Richard E. Crandall, Projects in scientific computation, TELOS. The Electronic Library of Science, Santa Clara, CA; Springer-Verlag, New York, 1994. With one Macintosh/IBM-PC floppy disk (3.5 inch). MR 1258083, DOI 10.1007/978-1-4612-4324-3
Richard E. Crandall, Topics in advanced scientific computation, Springer-Verlag, New York; TELOS. The Electronic Library of Science, Santa Clara, CA, 1996. MR 1392472, DOI 10.1007/978-1-4612-2334-4
R. Crandall, J. Doenias, C. Norrie, and J. Young, The twenty-second Fermat number is composite, Math. Comp. 64 (1995), no. 210, 863–868. MR 1277765, DOI 10.1090/S0025-5718-1995-1277765-9
Richard Crandall and Barry Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994), no. 205, 305–324. MR 1185244, DOI 10.1090/S0025-5718-1994-1185244-1
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.
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.
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.
Marije Elkenbracht-Huizing, An implementation of the number field sieve, Experiment. Math. 5 (1996), no. 3, 231–253. MR 1426450, DOI 10.1080/10586458.1996.10504590
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.
Gary B. Gostin, New factors of Fermat numbers, Math. Comp. 64 (1995), no. 209, 393–395. MR 1265015, DOI 10.1090/S0025-5718-1995-1265015-9
John C. Hallyburton Jr. and John Brillhart, Two new factors of Fermat numbers, Math. Comp. 29 (1975), 109–112. MR 369225, DOI 10.1090/S0025-5718-1975-0369225-1
Wilfrid Keller, Factors of Fermat numbers and large primes of the form $k\cdot 2^{n}+1$, Math. Comp. 41 (1983), no. 164, 661–673. MR 717710, DOI 10.1090/S0025-5718-1983-0717710-7
Wilfrid Keller, New Cullen primes, Math. Comp. 64 (1995), no. 212, 1733–1741, S39–S46. With a biographical sketch of James Cullen by T. G. Holt and a supplement by Keller and Wolfgang Niebuhr. MR 1308456, DOI 10.1090/S0025-5718-1995-1308456-3
Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0286318
Donald E. Knuth and Luis Trabb Pardo, Analysis of a simple factorization algorithm, Theoret. Comput. Sci. 3 (1976/77), no. 3, 321–348. MR 498355, DOI 10.1016/0304-3975(76)90050-5
M. Kraitchik, Théorie des nombres, Tome 2, Gauthier-Villars, Paris, 1926.
F. Landry, Note sur la décomposition du nombre $2^{64} + 1$ (Extrait), C. R. Acad. Sci. Paris 91 (1880), 138.
D. H. Lehmer, Tests for primality by the converse of Fermat’s theorem, Bull Amer. Math. Soc. 33 (1927), 327–340.
A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR 1321216, DOI 10.1007/BFb0091534
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), no. 203, 319–349. MR 1182953, DOI 10.1090/S0025-5718-1993-1182953-4
Arjen K. Lenstra and Mark S. Manasse, Factoring by electronic mail, Advances in cryptology—EUROCRYPT ’89 (Houthalen, 1989) Lecture Notes in Comput. Sci., vol. 434, Springer, Berlin, 1990, pp. 355–371. MR 1083962, DOI 10.1007/3-540-46885-4_{3}5
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
E. Lucas, Théorie des fonctions numériques simplement periodiques, Amer. J. Math. 1 (1878), 184–239 & 289–321.
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 247789, DOI 10.1090/S0025-5718-1969-0247789-3
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.
Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7
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/pub/pmontgom/ucladissertation.psl.Z.
Peter L. Montgomery, A survey of modern integer factorization algorithms, CWI Quarterly 7 (1994), no. 4, 337–366. MR 1334429
P. L. Montgomery, personal communication by e-mail, November 29, 1995.
François Morain, Courbes elliptiques et tests de primalité, Institut National de Recherche en Informatique et en Automatique (INRIA), Rocquencourt, 1990 (English, with French summary). Thèse, Université Claude Bernard-Lyon I, Lyon, 1990. MR 1288092
Michael A. Morrison and John Brillhart, A method of factoring and the factorization of $F_{7}$, Math. Comp. 29 (1975), 183–205. MR 371800, DOI 10.1090/S0025-5718-1975-0371800-5
Michael S. Paterson and Larry J. Stockmeyer, On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. Comput. 2 (1973), 60–66. MR 314238, DOI 10.1137/0202007
J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI 10.1017/s0305004100049252
J. M. Pollard, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 331–334. MR 392798, DOI 10.1007/bf01933667
Carl Pomerance, The quadratic sieve factoring algorithm, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 169–182. MR 825590, DOI 10.1007/3-540-39757-4_{1}7
Carl Pomerance, The number field sieve, Mathematics of Computation 1943–1993: a half-century of computational mathematics (Vancouver, BC, 1993) Proc. Sympos. Appl. Math., vol. 48, Amer. Math. Soc., Providence, RI, 1994, pp. 465–480. MR 1314884, DOI 10.1090/psapm/048/1314884
Carl Pomerance, A tale of two sieves, Notices Amer. Math. Soc. 43 (1996), no. 12, 1473–1485. MR 1416721
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, DOI 10.1007/978-1-4612-0251-6
R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120–126. MR 700103, DOI 10.1145/359340.359342
Tadasi Nakayama, On Frobeniusean algebras. I, Ann. of Math. (2) 40 (1939), 611–633. MR 16, DOI 10.2307/1968946
J. L. Selfridge, Factors of Fermat numbers, MTAC 7 (1953), 274–275.
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
L. A. Shepp and S. P. Lloyd, Ordered cycle lengths in a random permutation, Trans. Amer. Math. Soc. 121 (1966), 340–357. MR 195117, DOI 10.1090/S0002-9947-1966-0195117-8
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.
Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8
Robert D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), no. 177, 329–339. MR 866119, DOI 10.1090/S0025-5718-1987-0866119-8
Robert D. Silverman and Samuel S. Wagstaff Jr., A practical analysis of the elliptic curve factoring algorithm, Math. Comp. 61 (1993), no. 203, 445–462. MR 1122078, DOI 10.1090/S0025-5718-1993-1122078-7
H. Suyama, Informal preliminary report (8), personal communication, October 1985.
A. M. Vershik, Asymptotic distribution of decompositions of natural numbers into prime divisors, Dokl. Akad. Nauk SSSR 289 (1986), no. 2, 269–272 (Russian). MR 856456
H. C. Williams, How was $F_6$ factored?, Math. Comp. 61 (1993), no. 203, 463–474. MR 1182248, DOI 10.1090/S0025-5718-1993-1182248-9
H. C. Williams and J. S. Judd, Some algorithms for prime testing using generalized Lehmer functions, Math. Comp. 30 (1976), no. 136, 867–886. MR 414473, DOI 10.1090/S0025-5718-1976-0414473-6