An primality testing algorithm

Authors:
Leonard Adleman and Frank Thomson Leighton

Journal:
Math. Comp. **36** (1981), 261-266

MSC:
Primary 10A25; Secondary 10-04, 68C25

MathSciNet review:
595060

Full-text 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 non-residues*, Mathematika**4**(1957), 106–112. MR**0093504****[2]**D. A. Burgess,*On character sums and primitive roots*, Proc. London Math. Soc. (3)**12**(1962), 179–192. MR**0132732****[3]**D. A. Burgess,*On character sums and 𝐿-series*, Proc. London Math. Soc. (3)**12**(1962), 193–206. MR**0132733****[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 ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). MR**0480295****[5]**Karl K. Norton,*Numbers with small prime factors, and the least 𝑘th power non-residue*, Memoirs of the American Mathematical Society, No. 106, American Mathematical Society, Providence, R.I., 1971. MR**0286739****[6]**J. M. Pollard,*An algorithm for testing the primality of any integer*, Bull. London Math. Soc.**3**(1971), 337–340. MR**0294245****[7]**J. M. Pollard,*Theorems on factorization and primality testing*, Proc. Cambridge Philos. Soc.**76**(1974), 521–528. MR**0354514****[8]**Michael O. Rabin,*Probabilistic algorithms*, Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976) Academic Press, New York, 1976, pp. 21–39. MR**0464678****[9]**R. Solovay and V. Strassen,*A fast Monte-Carlo test for primality*, SIAM J. Comput.**6**(1977), no. 1, 84–85. MR**0429721**

Retrieve articles in *Mathematics of Computation*
with MSC:
10A25,
10-04,
68C25

Retrieve articles in all journals with MSC: 10A25, 10-04, 68C25

Additional Information

DOI:
http://dx.doi.org/10.1090/S0025-5718-1981-0595060-8

Keywords:
Algorithm,
Carmichael number,
composite,
factor,
prime,
residue

Article copyright:
© Copyright 1981
American Mathematical Society