Succinct proofs of primality for the factors of some Fermat numbers
Author:
Richard P. Brent
Journal:
Math. Comp. 38 (1982), 253255
MSC:
Primary 1004; Secondary 10A25, 65C99
MathSciNet review:
637304
Fulltext 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 multipleprecision arithmetic package,'' ACM Trans. Math. Software, v. 4, 1978, pp. 7181.
 [2]
Richard
P. Brent, An improved Monte Carlo factorization algorithm, BIT
20 (1980), no. 2, 176–184. MR 583032
(82a:10007), http://dx.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
(83h:10014), http://dx.doi.org/10.1090/S00255718198106065205
 [4]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [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
(51 #8017), http://dx.doi.org/10.1090/S00255718197503718005
 [7]
Vaughan
R. Pratt, Every prime has a succinct certificate, SIAM J.
Comput. 4 (1975), no. 3, 214–220. MR 0391574
(52 #12395)
 [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
(54 #2574), http://dx.doi.org/10.1090/S00255718197604144736
 [1]
 R. P. Brent, ``Algorithm 524: MP, A Fortran multipleprecision arithmetic package,'' ACM Trans. Math. Software, v. 4, 1978, pp. 7181.
 [2]
 R. P. Brent, ``An improved Monte Carlo factorization algorithm,'' BIT, v. 20, 1980, pp. 176184. MR 583032 (82a:10007)
 [3]
 R. P. Brent & J. M. Pollard, ``Factorization of the eighth Fermat number,'' Math. Comp., v. 36, 1981, pp. 627630. MR 606520 (83h:10014)
 [4]
 D. E. Knuth, The Art of Computer Programming, Vol. 2, AddisonWesley, 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. 183208. MR 0371800 (51:8017)
 [7]
 V. R. Pratt, ``Every prime has a succinct certificate,'' SIAM J. Comput., v. 4, 1975, pp. 214220. 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. 867886. MR 0414473 (54:2574)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
1004,
10A25,
65C99
Retrieve articles in all journals
with MSC:
1004,
10A25,
65C99
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198206373040
PII:
S 00255718(1982)06373040
Keywords:
Factorization,
Fermat numbers,
primality testing,
primitive root,
Monte Carlo methods
Article copyright:
© Copyright 1982
American Mathematical Society
