The Factorization of the Ninth Fermat Number

From MaRDI portal





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.



Cites work



Describes a project that uses

Uses Software






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)