Three new factors of Fermat numbers

Brent, R.; Crandall, R.; Dilcher, K.; Van Halewyn, C.

doi:10.1090/S0025-5718-00-01207-2

Three new factors of Fermat numbers
HTML articles powered by AMS MathViewer

by R. P. Brent, R. E. Crandall, K. Dilcher and C. Van Halewyn PDF

Math. Comp. 69 (2000), 1297-1304 Request permission

Abstract:

We report the discovery of a new factor for each of the Fermat numbers $F_{13}, F_{15}, F_{16}$. These new factors have 27, 33 and 27 decimal digits respectively. Each factor was found by the elliptic curve method. After division by the new factors and previously known factors, the remaining cofactors are seen to be composite numbers with $2391$, $9808$ and $19694$ decimal digits respectively.

References

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, Factorization of the tenth and eleventh Fermat numbers, Report TR-CS-96-02, Computer Sciences Laboratory, Australian National Univ., Canberra, Feb. 1997. ftp://nimbus.anu.edu.au/pub/Brent/rpb161tr.dvi.gz.
Richard P. Brent, Factorization of the tenth Fermat number, Math. Comp. 68 (1999), no. 225, 429–451. MR 1489968, DOI 10.1090/S0025-5718-99-00992-8
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
J. P. Buhler, personal communication to Crandall, 1993.
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179, DOI 10.1007/978-3-662-03338-8
C. Caldwell, The Dubner PC Cruncher – a microcomputer coprocessor card for doing integer arithmetic, review in J. Rec. Math. 25(1), 1993.
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
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
R. A. Rueppel (ed.), Advances in cryptology—EUROCRYPT ’92, Lecture Notes in Computer Science, vol. 658, Springer-Verlag, Berlin, 1993. MR 1243657, DOI 10.1007/3-540-47555-9
H. Dubner and R. Dubner, The Dubner PC Cruncher: Programmers Guide and Function Reference, February 15, 1993.
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
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
P. Hebroni, Sur les inverses des éléments dérivables dans un anneau abstrait, C. R. Acad. Sci. Paris 209 (1939), 285–287 (French). MR 14
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
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
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
A. Schönhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inf. 1 (1971), 139–144.
J. L. Selfridge, Factors of Fermat numbers, Math. Comp. 7 (1953), 274–275.
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 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 to Brent, October 1985.