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

MathSciNet review:
637304

Full-text PDF Free Access

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]**Richard P. Brent,*An improved Monte Carlo factorization algorithm*, BIT**20**(1980), no. 2, 176–184. MR**583032**, 10.1007/BF01933190**[3]**Richard P. Brent and John M. Pollard,*Factorization of the eighth Fermat number*, Math. Comp.**36**(1981), no. 154, 627–630. MR**606520**, 10.1090/S0025-5718-1981-0606520-5**[4]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[5]**D. N. Lehmer,*List of Prime Numbers from 1 to 10,006,721*, Hafner, New York, 1956.**[6]**Michael A. Morrison and John Brillhart,*A method of factoring and the factorization of 𝐹₇*, Math. Comp.**29**(1975), 183–205. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. MR**0371800**, 10.1090/S0025-5718-1975-0371800-5**[7]**Vaughan R. Pratt,*Every prime has a succinct certificate*, SIAM J. Comput.**4**(1975), no. 3, 214–220. MR**0391574****[8]**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**0414473**, 10.1090/S0025-5718-1976-0414473-6

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