The factorization of the ninth Fermat number
HTML articles powered by AMS MathViewer
- by A. K. Lenstra, H. W. Lenstra, M. S. Manasse and J. M. Pollard PDF
- Math. Comp. 61 (1993), 319-349 Request permission
Addendum: Math. Comp. 64 (1995), 1357.
Abstract:
In this paper we exhibit the full prime factorization of the ninth Fermat number ${F_9} = {2^{512}} + 1$. It is the product of three prime factors that have 7, 49, and 99 decimal digits. We found the two largest prime factors by means of the number field sieve, which is a factoring algorithm that depends on arithmetic in an algebraic number field. In the present case, the number field used was ${\mathbf {Q}}(\sqrt [5]{2})$. The calculations were done on approximately 700 workstations scattered around the world, and in one of the final stages a supercomputer was used. The entire factorization took four months.References
- George E. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. MR 0557013 A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Research report 1256, INRIA, June 1990. R. P. Brent, Some integer factorization algorithms using elliptic curves, Austral. Comp. Sci. Comm. 8 (1986), 149-163. —, Factorization of the eleventh Fermat number (preliminary report), Abstracts Amer. Math. Soc. 10 (1989), 89T-11-73.
- Richard P. Brent, Parallel algorithms for integer factorisation, Number theory and cryptography (Sydney, 1989) London Math. Soc. Lecture Note Ser., vol. 154, Cambridge Univ. Press, Cambridge, 1990, pp. 26–37. MR 1055398
- 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
- 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
- Johannes Buchmann, A generalization of Voronoĭ’s unit algorithm. I, J. Number Theory 20 (1985), no. 2, 177–191. MR 790781, DOI 10.1016/0022-314X(85)90039-3 J. A. Buchmann and H. W. Lenstra, Jr., Approximating rings of integers in number fields, in preparation. J. P. Buhler, H. W. Lenstra, Jr., and C. Pomerance, Factoring integers with the number field sieve (to appear).
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
- H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), no. 177, 103–121, S1–S4. MR 866102, DOI 10.1090/S0025-5718-1987-0866102-2
- H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297–330. MR 726006, DOI 10.1090/S0025-5718-1984-0726006-X
- J. H. Conway, On numbers and games, London Mathematical Society Monographs, No. 6, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0450066 A. Cunningham and A. E. Western, On Fermat’s numbers, Proc. London Math. Soc. (2) 1 (1904), 175. 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. L. E. Dickson, History of the theory of numbers, vol. I, Carnegie Inst. of Washington, Washington, 1919. L. Euler, Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus, Comm. Acad. Sci. Petropol. 6 (1732/1733), 103-107; Leonhardi Euleri Opera Omnia, Ser. I, vol. II, Teubner, Leipzig, 1915, pp. 1-5. C. F. Gauss, Disquisitiones arithmeticae Fleischer, Leipzig, 1801. A. Gérardin, Méthodes de Landry, L’intermédiaire des Mathématiciens 16 (1909), 199-201.
- Gary B. Gostin and Philip B. McLaughlin Jr., Six new factors of Fermat numbers, Math. Comp. 38 (1982), no. 158, 645–649. MR 645680, DOI 10.1090/S0025-5718-1982-0645680-8
- 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 W. Keller, Factors of Fermat numbers and large primes of the form $k \cdot {2^n} + 1$. II, submitted for publication. B. A. LaMacchia and A. M. Odlyzko, Solving large sparse linear systems over finite fields, Advances in Cryptology, Proc. Crypto ’90, Lecture Notes in Comput. Sci., vol. 537, Springer-Verlag, Berlin and New York, 1991, pp. 109-133. F. Landry, Note sur la décomposition du nombre ${2^{64}} + 1$ (Extrait), C. R. Acad. Sci. Paris 91 (1880), 138.
- A. K. Lenstra, Factorization of polynomials, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 169–198. MR 700263
- A. K. Lenstra and H. W. Lenstra Jr., Algorithms in number theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 673–715. MR 1127178 A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The number field sieve, (to appear). Extended abstract: Proc. 22nd Annual ACM Sympos. Theory of Computing (STOC) (Baltimore, May 14-16, 1990), pp. 564-572.
- 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
- A. K. Lenstra and M. S. Manasse, Factoring with two large primes, Math. Comp. 63 (1994), no. 208, 785–798. MR 1250773, DOI 10.1090/S0025-5718-1994-1250773-9
- 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
- H. W. Lenstra Jr. and Carl Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), no. 3, 483–516. MR 1137100, DOI 10.1090/S0894-0347-1992-1137100-0 H. W. Lenstra, Jr., and R. Tijdeman (eds.), Computational methods in number theory, Math. Centre Tracts, no. 154/155, Mathematisch Centrum, Amsterdam, 1983.
- 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
- Peter L. Montgomery and Robert D. Silverman, An FFT extension to the $P-1$ factoring algorithm, Math. Comp. 54 (1990), no. 190, 839–854. MR 1011444, DOI 10.1090/S0025-5718-1990-1011444-3
- 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 T. Pepin, Sur la formule ${2^{{2^n}}} + 1$, C. R. Acad. Sci. Paris 85 (1877), 329-331.
- C. Pomerance, Analysis and comparison of some integer factoring algorithms, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR 700260
- Carl Pomerance and J. W. Smith, Reduction of huge, sparse matrices over finite fields via created catastrophes, Experiment. Math. 1 (1992), no. 2, 89–94. MR 1203868
- Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
- Hans Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR 897531, DOI 10.1007/978-1-4757-1089-2 RSA Data Security Corporation, Inc., sci.crypt, May 18, 1991; information available by sending electronic mail to challenge-rsa-list@rsa.com.
- C.-P. Schnorr and H. W. Lenstra Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), no. 167, 289–311. MR 744939, DOI 10.1090/S0025-5718-1984-0744939-5
- Daniel Shanks, On Gauss and composition. I, II, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 163–178, 179–204. MR 1123074
- 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
- Ian Stewart and David Tall, Algebraic number theory, Chapman and Hall Mathematics Series, Chapman and Hall, London; John Wiley & Sons, Inc., New York, 1979. MR 549770 P. Tannery and C. Henry (eds.), Oeuvres de Fermat, vol. II, Correspondance, Gauthier-Villars, Paris, 1894.
- André Weil, Number theory, Birkhäuser Boston, Inc., Boston, MA, 1984. An approach through history; From Hammurapi to Legendre. MR 734177, DOI 10.1007/978-0-8176-4571-7
- Doug Wiedemann, An iterated quadratic extension of $\textrm {GF}(2)$, Fibonacci Quart. 26 (1988), no. 4, 290–295. MR 967647
- 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
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 61 (1993), 319-349
- MSC: Primary 11Y05; Secondary 11Y40
- DOI: https://doi.org/10.1090/S0025-5718-1993-1182953-4
- MathSciNet review: 1182953