In 1970, Morrison and Brillhart factored the seventh Fermat number by the continued fraction method, leaving F8 as as the first Fermat number which was neither prime nor completely factored. F8 was known to be composite (with 78 decimal digits), but no factors were known.
On 9 July 1980, Richard Brent and John Pollard factored F8, finding
F8 = 1238926361552897 . p62where p62 is a 62-decimal digit prime number.
A modification of Pollard's "rho" method was used to find the factorisation in two hours on a Univac 1100/42 computer. The computation required about 23 million multiplications modulo F8.
I am now entirely persuaded to employ the method,
a handy trick, on gigantic composite numbers
may be helpful if you wish to remember the smaller factor of F8.
Later, a simpler proof was provided by Brent, using the factorisation
p62 - 1 = 31618624099079 . p43
Further details can be found in the paper:
Richard P. Brent and John M. Pollard, Factorization of the Eighth Fermat Number, Mathematics of Computation 36 (1981), 627-630.
Return to Richard Brent's index page