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 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, https://doi.org/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, https://doi.org/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. MR 371800, https://doi.org/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 391574, https://doi.org/10.1137/0204018
- [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 414473, https://doi.org/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