Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Succinct proofs of primality for the factors of some Fermat numbers


Author: Richard P. Brent
Journal: Math. Comp. 38 (1982), 253-255
MSC: Primary 10-04; Secondary 10A25, 65C99
DOI: https://doi.org/10.1090/S0025-5718-1982-0637304-0
MathSciNet review: 637304
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We give short and easily verified proofs of primality for the factors of the Fermat numbers $ {F_5},{F_6},{F_7}$ and $ {F_8}$.


References [Enhancements On Off] (What's this?)

  • [1] R. P. Brent, ``Algorithm 524: MP, A Fortran multiple-precision arithmetic package,'' ACM Trans. Math. Software, v. 4, 1978, pp. 71-81.
  • [2] R. P. Brent, ``An improved Monte Carlo factorization algorithm,'' BIT, v. 20, 1980, pp. 176-184. MR 583032 (82a:10007)
  • [3] R. P. Brent & J. M. Pollard, ``Factorization of the eighth Fermat number,'' Math. Comp., v. 36, 1981, pp. 627-630. MR 606520 (83h:10014)
  • [4] D. E. Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley, Menlo Park, 1969, Sec. 4.5.4. MR 633878 (83i:68003)
  • [5] D. N. Lehmer, List of Prime Numbers from 1 to 10,006,721, Hafner, New York, 1956.
  • [6] 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)
  • [7] V. R. Pratt, ``Every prime has a succinct certificate,'' SIAM J. Comput., v. 4, 1975, pp. 214-220. MR 0391574 (52:12395)
  • [8] 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: 10-04, 10A25, 65C99

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


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1982-0637304-0
Keywords: Factorization, Fermat numbers, primality testing, primitive root, Monte Carlo methods
Article copyright: © Copyright 1982 American Mathematical Society

American Mathematical Society