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

**[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 ,''*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)**

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