The Factorization of the Ninth Fermat Number
This paper gives a detailed and very instructive description of how the ninth Fermat number \(F_ 9= 2^{512}+1\) was factorized. Two new factors of \(F_ 9\), with 49 and 99 decimal digits, were found in the morning of June 15, 1990, after a concerted number crunching attack of approximately 700 workstations and a supercomputer over a period of four months. The method used was the number field sieve (NFS), which depends on arithmetic in an algebraic number field. For \(F_ 9\), this field was \(\mathbb{Q}({\root 5 \of {2}})\). The paper starts with a survey of Fermat numbers and their place in number theory and history. Next a general class of methods for factoring \(n\) is discussed, based on finding integers \(x\) for which \(x^ 2\equiv 1\bmod n\), NFS being a special case. Using the actual prime factors of \(F_ 9\) it is explained why earlier attempts to factor it with other methods like the elliptic curve method have failed. After listing several basic facts from algebraic number theory, the authors describe the number field sieve, and how they applied it to \(F_ 9\). Next the actual sieving process is discussed, followed by the final step which involves the solution of a huge sparse \(226688\times 199203\) linear system over \(\mathbb{F}_ 2\) with an average of 50 nonzero elements per row. This system was reduced to a smaller system of size \(72413\times 72213\) by eliminating with certain sparse columns that cause fill-in only in certain so-called heavy columns. The final system was solved by means of ordinary Gaussian elimination on a 65536-processor Connection Machine at the expense of three hours CPU-time. This decomposition of \(F_ 9\) into prime factors is to be considered a major achievement which was only possible by a combination of great skill in algebraic number theory, computational mathematics, and computer science.
- A course in computational algebraic number theory
- A Method of Factoring and the Factorization of F 7
- A Monte Carlo Factoring Algorithm With Linear Storage
- A Rigorous Time Bound for Factoring Integers
- An FFT Extension to the P - 1 Factoring Algorithm
- Approximating rings of integers in number fields
- Elliptic Curves and Primality Proving
- Factoring integers with elliptic curves
- Factoring integers with the number field sieve
- Factoring with Two Large Primes
- Factorization of the Eighth Fermat Number
- Factorizations of 𝑏ⁿ±1, 𝑏=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers
- Factors of Fermat Numbers and Large Primes of the Form k ⋅2 n + 1
- How was F 6 Factored?
- scientific article; zbMATH DE number 4130460 (Why is no real title available?)
- scientific article; zbMATH DE number 3841940 (Why is no real title available?)
- scientific article; zbMATH DE number 4165009 (Why is no real title available?)
- scientific article; zbMATH DE number 4075228 (Why is no real title available?)
- scientific article; zbMATH DE number 3521877 (Why is no real title available?)
- scientific article; zbMATH DE number 3577263 (Why is no real title available?)
- scientific article; zbMATH DE number 3641577 (Why is no real title available?)
- scientific article; zbMATH DE number 503245 (Why is no real title available?)
- scientific article; zbMATH DE number 1142300 (Why is no real title available?)
- scientific article; zbMATH DE number 3801619 (Why is no real title available?)
- Implementation of a new primality test
- Primality Testing and Jacobi Sums
- Prime numbers and computer methods for factorization
- Probabilistic algorithm for testing primality
- Reduction of Huge, Sparse Matrices over Finite Fields Via Created Catastrophes
- Six New Factors of Fermat Numbers
- Speeding the Pollard and Elliptic Curve Methods of Factorization
- The Multiple Polynomial Quadratic Sieve
- Two New Factors of Fermat Numbers
- Approximating rings of integers in number fields
- The composite character of the twenty-second Fermat number
- On the complexity of matrix reduction over finite fields
- Periodic binary harmonic functions on lattices
- How was F 6 Factored?
- Finding special factors of values of polynomials at integer points
- Improved information set decoding for code-based cryptosystems with constrained memory
- Factorization of the Eighth Fermat Number
- Algorithms in Algebraic Number Theory
- A Rigorous Time Bound for Factoring Integers
- Factorization of the tenth Fermat number
- Factoring with Two Large Primes
- New Factors of Fermat Numbers
- scientific article; zbMATH DE number 3995751 (Why is no real title available?)
- Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method
- The twenty-fourth Fermat number is composite
- The Twenty-Second Fermat Number is Composite
- Addendum: The Factorization of the Ninth Fermat Number
- Three new factors of Fermat numbers
- Why does a prime \(p\) divide a Fermat number?
- Analyzing massively collaborative mathematics projects
- Computation of a 768-bit prime field discrete logarithm
This page was built for publication: The Factorization of the Ninth Fermat Number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3137471)