Explicit primality criteria for

Authors:
Andreas Stein and H. C. Williams

Journal:
Math. Comp. **69** (2000), 1721-1734

MSC (1991):
Primary 11Y11; Secondary 11Y16

Published electronically:
February 23, 2000

MathSciNet review:
1697651

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Deterministic polynomial time primality criteria for have been known since the work of Lucas in 1876-1878. Little is known, however, about the existence of deterministic polynomial time primality tests for numbers of the more general form , where is any fixed prime. When we show that it is always possible to produce a Lucas-like deterministic test for the primality of which requires that only modular multiplications be performed modulo , as long as we can find a prime of the form such that is not divisible by . We also show that for all with such a can be found very readily, and that the most difficult case in which to find a appears, somewhat surprisingly, to be that for . Some explanation is provided as to why this case is so difficult.

**1.**Eric Bach,*Explicit bounds for primality testing and related problems*, Math. Comp.**55**(1990), no. 191, 355–380. MR**1023756**, 10.1090/S0025-5718-1990-1023756-8**2.**Wieb Bosma,*Explicit primality criteria for ℎ⋅2^{𝑘}±1*, Math. Comp.**61**(1993), no. 203, 97–109, S7–S9. MR**1197510**, 10.1090/S0025-5718-1993-1197510-3**3.**D. H. Lehmer.

An extended theory of Lucas' functions.*Annals of Mathematics*, 31:419-448, 1930.**4.**E. Lucas.

Nouveaux théoremes d`arithmétique supérieure.*Comptes Rendus Acad. des Sciences, Paris*, 83:1286-1288, 1876.**5.**H. C. Williams,*An algorithm for determining certain large primes*, Proceedings Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971) Louisiana State Univ., Baton Rouge, La., 1971, pp. 533–556. MR**0319874****6.**H. C. Williams,*The primality of 𝑁=2𝐴3ⁿ-1*, Canad. Math. Bull.**15**(1972), 585–589. MR**0311559****7.**H. C. Williams,*The primality of certain integers of the form 2𝐴𝑟ⁿ-1*, Acta Arith.**39**(1981), no. 1, 7–17. MR**638738****8.**H. C. Williams,*A class of primality tests for trinomials which includes the Lucas-Lehmer test*, Pacific J. Math.**98**(1982), no. 2, 477–494. MR**650024****9.**H. C. Williams,*Effective primality tests for some integers of the forms 𝐴5ⁿ-1 and 𝐴7ⁿ-1*, Math. Comp.**48**(1987), no. 177, 385–403. MR**866123**, 10.1090/S0025-5718-1987-0866123-X**10.**H. C. Williams.*Édouard Lucas and Primality Testing*, volume 22 of*Canadian Mathematical Society Series of Monographs and Advanced Texts*.

Wiley, NY, 1998. CMP**98:15**

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
11Y11,
11Y16

Retrieve articles in all journals with MSC (1991): 11Y11, 11Y16

Additional Information

**Andreas Stein**

Affiliation:
University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada N2L 3G1

Email:
astein@cacr.math.uwaterloo.ca

**H. C. Williams**

Affiliation:
University of Manitoba, Department of Computer Science, Winnipeg, Manitoba, Canada R3T 2N2

Email:
williams@cs.umanitoba.ca

DOI:
http://dx.doi.org/10.1090/S0025-5718-00-01212-6

Keywords:
Primality test,
Mersenne numbers,
Lucas functions,
Gauss sums,
covering sets

Received by editor(s):
October 24, 1997

Received by editor(s) in revised form:
October 23, 1998

Published electronically:
February 23, 2000

Additional Notes:
Research supported by NSERC of Canada Grant $#A7649$.

Article copyright:
© Copyright 2000
American Mathematical Society