An primality testing algorithm
Authors:
Leonard Adleman and Frank Thomson Leighton
Journal:
Math. Comp. 36 (1981), 261266
MSC:
Primary 10A25; Secondary 1004, 68C25
MathSciNet review:
595060
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In this paper, we describe an deterministic algorithm to decide primality. The algorithm incorporates several recent results in complexity theory.
 [1]
D.
A. Burgess, The distribution of quadratic residues and
nonresidues, Mathematika 4 (1957), 106–112. MR 0093504
(20 #28)
 [2]
D.
A. Burgess, On character sums and primitive roots, Proc.
London Math. Soc. (3) 12 (1962), 179–192. MR 0132732
(24 #A2569)
 [3]
D.
A. Burgess, On character sums and 𝐿series, Proc.
London Math. Soc. (3) 12 (1962), 193–206. MR 0132733
(24 #A2570)
 [4]
Gary
L. Miller, Riemann’s hypothesis and tests for primality,
J. Comput. System Sci. 13 (1976), no. 3,
300–317. Working papers presented at the ACMSIGACT Symposium on the
Theory of Computing (Albuquerque, N.M., 1975). MR 0480295
(58 #470a)
 [5]
Karl
K. Norton, Numbers with small prime factors, and the least
𝑘th power nonresidue, Memoirs of the American Mathematical
Society, No. 106, American Mathematical Society, Providence, R.I., 1971. MR 0286739
(44 #3948)
 [6]
J.
M. Pollard, An algorithm for testing the primality of any
integer, Bull. London Math. Soc. 3 (1971),
337–340. MR 0294245
(45 #3314)
 [7]
J.
M. Pollard, Theorems on factorization and primality testing,
Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 0354514
(50 #6992)
 [8]
Michael
O. Rabin, Probabilistic algorithms, Algorithms and complexity
(Proc. Sympos., CarnegieMellon Univ., Pittsburgh, Pa., 1976) Academic
Press, New York, 1976, pp. 21–39. MR 0464678
(57 #4603)
 [9]
R.
Solovay and V.
Strassen, A fast MonteCarlo test for primality, SIAM J.
Comput. 6 (1977), no. 1, 84–85. MR 0429721
(55 #2732)
 [1]
 D. A. Burgess, "The distribution of quadratic residues and nonresidues," Mathematika, v. 4, 1957, pp. 106112. MR 0093504 (20:28)
 [2]
 D. A. Burgess, "On character sums and primitive roots," Proc. London Math. Soc. (3), v. 12, 1962, pp. 179192. MR 0132732 (24:A2569)
 [3]
 D. A. Burgess, "On character sums and Lseries," Proc. London Math. Soc. (3), v. 12, 1962, pp. 193206. MR 0132733 (24:A2570)
 [4]
 G. L. Miller, "Riemann's hypothesis and tests for primality," J. Comput. System Sci., v. 13, 1976, pp. 300317. MR 0480295 (58:470a)
 [5]
 K. K. Norton, "Numbers with small prime factors and the least kth power nonresidue," Mem. Amer. Math. Soc., No. 106, Amer. Math. Soc., Providence, R. I., 1971. MR 0286739 (44:3948)
 [6]
 J. M. Pollard, "An algorithm for testing the primality of any integer," Bull. London Math. Soc., v. 3, 1971, pp. 337340. MR 0294245 (45:3314)
 [7]
 J. M. Pollard, "Theorems on factorization and primality testing," Proc. Cambridge Philos. Soc., v. 76, 1974, pp. 521528. MR 0354514 (50:6992)
 [8]
 M. O. Rabin, "Probabilistic algorithms," Algorithms and Complexity, New Directions and Present Results (J. Traub, Ed.), Academic Press, New York, 1976, pp. 2140. MR 0464678 (57:4603)
 [9]
 R. Solovay & V. Strassen, "A fast Monte Carlo test for primality," SIAM J. Comput., v. 6, 1977, pp. 8485. MR 0429721 (55:2732)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
10A25,
1004,
68C25
Retrieve articles in all journals
with MSC:
10A25,
1004,
68C25
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198105950608
PII:
S 00255718(1981)05950608
Keywords:
Algorithm,
Carmichael number,
composite,
factor,
prime,
residue
Article copyright:
© Copyright 1981
American Mathematical Society
