Factorisation of F8

F8 = 228 + 1 = 2256 + 1 is the eighth Fermat number.

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

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

Epigram

The epigram

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.

The Larger Factor

The larger factor p62 of F8 was first proved prime by Hugh Williams using the method of Williams and Judd.

Later, a simpler proof was provided by Brent, using the factorisation

p62 - 1 = 31618624099079 . p43

References and Further Details

A preliminary announcement of the factorisation of F8 appeared in AMS Abstracts 1 (1980), 565, 80T-A212.

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