Succinct proofs of primality for the factors of some Fermat numbers

Brent, Richard P.

doi:10.1090/S0025-5718-1982-0637304-0

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 ${F_5},{F_6},{F_7}$ and ${F_8}$ .

[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