Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

The factorization of the ninth Fermat number


Authors: A. K. Lenstra, H. W. Lenstra, M. S. Manasse and J. M. Pollard
Journal: Math. Comp. 61 (1993), 319-349
MSC: Primary 11Y05; Secondary 11Y40
DOI: https://doi.org/10.1090/S0025-5718-1993-1182953-4
Addendum: Math. Comp. 64 (1995), 1357.
MathSciNet review: 1182953
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] G. E. Andrews, The theory of partitions, Addison-Wesley, Reading, MA, 1976. MR 0557013 (58:27738)
  • [2] A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Research report 1256, INRIA, June 1990.
  • [3] R. P. Brent, Some integer factorization algorithms using elliptic curves, Austral. Comp. Sci. Comm. 8 (1986), 149-163.
  • [4] -, Factorization of the eleventh Fermat number (preliminary report), Abstracts Amer. Math. Soc. 10 (1989), 89T-11-73.
  • [5] -, Parallel algorithms for integer factorisation, Number Theory and Cryptography (J. H. Loxton, ed.), London Math. Soc. Lecture Note Series, vol. 154, Cambridge Univ. Press, Cambridge, 1990, pp. 26-37. MR 1055398 (91h:11148)
  • [6] R. P. Brent and J. M. Pollard, Factorization of the eighth Fermat number, Math. Comp. 36 (1981), 627-630. MR 606520 (83h:10014)
  • [7] 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., Contemp. Math., vol. 22, Amer. Math. Soc., Providence, RI, 1988. MR 996414 (90d:11009)
  • [8] J. A. Buchmann, A generalization of Voronoi's unit algorithm. II, J. Number Theory 20 (1985), 192-209. MR 790782 (86g:11062b)
  • [9] J. A. Buchmann and H. W. Lenstra, Jr., Approximating rings of integers in number fields, in preparation.
  • [10] J. P. Buhler, H. W. Lenstra, Jr., and C. Pomerance, Factoring integers with the number field sieve (to appear).
  • [11] H. Cohen, A course in computational algebraic number theory, Springer-Verlag (to appear). MR 1228206 (94i:11105)
  • [12] H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), 103-121, S1-S4. MR 866102 (88c:11080)
  • [13] H. Cohen and H. W. Lenstra, Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), 297-330. MR 726006 (86g:11078)
  • [14] J. H. Conway, On numbers and games, Academic Press, London, 1976. MR 0450066 (56:8365)
  • [15] A. Cunningham and A. E. Western, On Fermat's numbers, Proc. London Math. Soc. (2) 1 (1904), 175.
  • [16] 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.
  • [17] L. E. Dickson, History of the theory of numbers, vol. I, Carnegie Inst. of Washington, Washington, 1919.
  • [18] 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.
  • [19] C. F. Gauss, Disquisitiones arithmeticae Fleischer, Leipzig, 1801.
  • [20] A. Gérardin, Méthodes de Landry, L'intermédiaire des Mathématiciens 16 (1909), 199-201.
  • [21] G. B. Gostin and P. B. McLaughlin, Jr., Six new factors of Fermat numbers, Math. Comp. 38 (1982), 645-649. MR 645680 (83c:10003)
  • [22] J. C. Hallyburton, Jr., and J. Brillhart, Two new factors of Fermat numbers, Math. Comp. 29 (1975), 109-112; corrigendum, ibid. 30 (1976), 198. MR 0369225 (51:5460)
  • [23] W. Keller, Factors of Fermat numbers and large primes of the form $ k \cdot {2^n} + 1$. II, submitted for publication.
  • [24] 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.
  • [25] F. Landry, Note sur la décomposition du nombre $ {2^{64}} + 1$ (Extrait), C. R. Acad. Sci. Paris 91 (1880), 138.
  • [26] A. K. Lenstra, Factorization of polynomials, pp. 169-198 in [33]. MR 700263 (85a:12002)
  • [27] A. K. Lenstra and H. W. Lenstra, Jr., Algorithms in number theory, Handbook of Theoretical Computer Science, Volume A, Algorithms and Complexity (J. Van Leeuwen, ed.), Elsevier, Amsterdam, 1990, Chapter 12. MR 1127178
  • [28] 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.
  • [29] A. K. Lenstra and M. S. Manasse, Factoring by electronic mail, Advances in Cryptology, Eurocrypt '89, Lecture Notes in Comput. Sci., vol. 434, Springer-Verlag, Berlin and New York, 1990, pp. 355-371. MR 1083962 (91i:11182)
  • [30] -, Factoring with two large primes, Math. Comp. (to appear). MR 1250773 (95a:11107)
  • [31] H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. MR 916721 (89g:11125)
  • [32] H. W. Lenstra, Jr., and C. Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), 483-516. MR 1137100 (92m:11145)
  • [33] H. W. Lenstra, Jr., and R. Tijdeman (eds.), Computational methods in number theory, Math. Centre Tracts, no. 154/155, Mathematisch Centrum, Amsterdam, 1983.
  • [34] P. L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), 243-264. MR 866113 (88e:11130)
  • [35] P. L. Montgomery and R. D. Silverman, An FFT extension to the $ P - 1$ factoring algorithm, Math. Comp. 54 (1990), 839-854. MR 1011444 (90j:11142)
  • [36] M. A. Morrison and J. Brillhart, A method of factoring and the factorization of $ {F_7}$, Math. Comp. 29 (1975), 183-205. MR 0371800 (51:8017)
  • [37] T. Pepin, Sur la formule $ {2^{{2^n}}} + 1$, C. R. Acad. Sci. Paris 85 (1877), 329-331.
  • [38] C. Pomerance, Analysis and comparison of some integer factoring algorithms, pp. 89-139 in [33]. MR 700260 (84i:10005)
  • [39] C. Pomerance and J. W. Smith, Reduction of huge, sparse matrices over finite fields via created catastrophes, Experiment. Math. 1 (1992), 89-94. MR 1203868
  • [40] M. O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), 128-138. MR 566880 (81f:10003)
  • [41] H. Riesel, Prime numbers and computer methods for factorization, Birkhäuser, Boston, 1985. MR 897531 (88k:11002)
  • [42] RSA Data Security Corporation, Inc., sci.crypt, May 18, 1991; information available by sending electronic mail to challenge-rsa-list@rsa.com.
  • [43] C. P. Schnorr and H. W. Lenstra, Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), 289-311. MR 744939 (85d:11106)
  • [44] D. Shanks, On Gauss and composition, I, Number theory and applications, NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci. 265, Kluwer, Dordrecht, 1989, see p. 174. MR 1123074 (92e:11150)
  • [45] R. D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), 329-339. MR 866119 (88c:11079)
  • [46] I. N. Stewart and D. O. Tall, Algebraic number theory, Chapman and Hall, London, 1979. MR 549770 (81g:12001)
  • [47] P. Tannery and C. Henry (eds.), Oeuvres de Fermat, vol. II, Correspondance, Gauthier-Villars, Paris, 1894.
  • [48] A. Weil, Number theory: an approach through history, Birkhäuser, Boston, 1983. MR 734177 (85c:01004)
  • [49] D. Wiedemann, An iterated quadratic extension of GF(2), Fibonacci Quart. 26 (1988), 290-295. MR 967647 (89m:11122)
  • [50] H. C. Williams, How was $ {F_6}$ factored?, Math. Comp. 61 (1993), 463-474. MR 1182248 (93k:01046)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05, 11Y40

Retrieve articles in all journals with MSC: 11Y05, 11Y40


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1993-1182953-4
Keywords: Fermat number, factoring algorithm
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society