The factorization of the ninth Fermat number

Lenstra, A. K.; Lenstra, H. W.; Manasse, M. S.; Pollard, J. M.

doi:10.1090/S0025-5718-1993-1182953-4

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

Elliptic curves and primality proving

Some integer factorization algorithms using elliptic curves

8

Factorization of the eleventh Fermat number (preliminary report)

10

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

Approximating rings of integers in number fields

Factoring integers with the number field sieve

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

On Fermat’s numbers

1

Factorisation of

up to high powers

n

History of the theory of numbers

Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus

6

Disquisitiones arithmeticae

16

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

Factors of Fermat numbers and large primes of the form

Solving large sparse linear systems over finite fields

Note sur la décomposition du nombre

91

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

The number field sieve,

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

Computational methods in number theory

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

Sur la formule

85

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

Oeuvres de Fermat

Correspondance

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