Explicit primality criteria for

Authors:
Andreas Stein and H. C. Williams

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

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

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

Published electronically:
February 23, 2000

MathSciNet review:
1697651

Full-text PDF

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.**E. Bach.

Explicit bounds for primality testing and related problems.*Mathematics of Computation*, 55:355-380, 1990. MR**91m:11096****2.**W. Bosma.

Explicit primality criteria for .*Mathematics of Computation*, 61:97-109, 1993. MR**94c:11005****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. Proc. Second Louisiana Conf. Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, LA, 1971, pp. 533-556. MR**47:8415****6.**H. C. Williams.

The primality of .*Canadian Math. Bull.*, 15:585-589, 1972. MR**47:121****7.**H. C. Williams.

The primality of certain integers of the form .*Acta Arith.*, 39:7-17, 1981. MR**84h:10012****8.**H. C. Williams.

A class of primality tests for trinomials which includes the Lucas-Lehmer test.*Pacific J. Math.*, 98:477-494, 1982. MR**83f:10008****9.**H. C. Williams.

Effective primality tests for some integers of the form and .*Mathematics of Computation*, 48:385-403, 1987. MR**88b:11089****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*
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:
https://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