Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Factorization of the eighth Fermat number


Authors: Richard P. Brent and John M. Pollard
Journal: Math. Comp. 36 (1981), 627-630
MSC: Primary 10A25; Secondary 10-04, 65C05
DOI: https://doi.org/10.1090/S0025-5718-1981-0606520-5
MathSciNet review: 606520
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] R. P. Brent, "An improved Monte Carlo factorization algorithm," BIT, v. 20, 1980, pp. 176-184. MR 583032 (82a:10007)
  • [2] J. C. Hallyburton & J. Brillhart, "Two new factors of Fermat numbers," Math. Comp., v. 29, 1975, pp. 109-112. MR 0369225 (51:5460)
  • [3] M. A. Morrison & J. Brillhart, "A method of factoring and the factorization of $ {F_7}$," Math. Comp., v. 29, 1975, pp. 183-208. MR 0371800 (51:8017)
  • [4] J. M. Pollard, "A Monte Carlo method for factorization," BIT, v. 15, 1975, pp. 331-334. MR 50 #6992. MR 0392798 (52:13611)
  • [5] J. M. Pollard, "Monte Carlo methods for index computation $ \pmod p$," Math. Comp., v. 32, 1978, pp. 918-924. MR 52 #13611. MR 0491431 (58:10684)
  • [6] M. Rabin, "Probabilistic algorithms," Algorithms and Complexity (J. F. Traub, Ed.), Academic Press, New York, 1976, pp. 31-40. MR 0464678 (57:4603)
  • [7] H. C. Williams & J. S. Judd, "Some algorithms for prime testing using generalized Lehmer functions," Math. Comp., v. 30, 1976, pp. 867-886. MR 0414473 (54:2574)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10A25, 10-04, 65C05

Retrieve articles in all journals with MSC: 10A25, 10-04, 65C05


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1981-0606520-5
Keywords: Fermat numbers, factorization, Monte Carlo methods
Article copyright: © Copyright 1981 American Mathematical Society

American Mathematical Society