Factorization of the eighth Fermat number

Brent, Richard P.; Pollard, John M.

doi:10.1090/S0025-5718-1981-0606520-5

Factorization of the eighth Fermat number
HTML articles powered by AMS MathViewer

by Richard P. Brent and John M. Pollard PDF

Math. Comp. 36 (1981), 627-630 Request permission

Abstract:

We describe a Monte Carlo factorization algorithm which was used to factorize the Fermat number ${F_8} = {2^{256}} + 1$. Previously ${F_8}$ was known to be composite, but its factors were unknown.

References

Richard P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), no. 2, 176–184. MR 583032, DOI 10.1007/BF01933190
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
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
J. M. Pollard, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 331–334. MR 392798, DOI 10.1007/bf01933667
J. M. Pollard, Monte Carlo methods for index computation $(\textrm {mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, DOI 10.1090/S0025-5718-1978-0491431-9
Michael O. Rabin, Probabilistic algorithms, Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976) Academic Press, New York, 1976, pp. 21–39. MR 0464678
H. C. Williams and J. S. Judd, Some algorithms for prime testing using generalized Lehmer functions, Math. Comp. 30 (1976), no. 136, 867–886. MR 414473, DOI 10.1090/S0025-5718-1976-0414473-6