Explicit primality criteria for
Authors:
Andreas Stein and H. C. Williams
Journal:
Math. Comp. 69 (2000), 17211734
MSC (1991):
Primary 11Y11; Secondary 11Y16
Published electronically:
February 23, 2000
MathSciNet review:
1697651
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Deterministic polynomial time primality criteria for have been known since the work of Lucas in 18761878. 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 Lucaslike 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
(91m:11096), http://dx.doi.org/10.1090/S00255718199010237568
 2.
Wieb
Bosma, Explicit primality criteria for
ℎ⋅2^{𝑘}±1, Math.
Comp. 61 (1993), no. 203, 97–109, S7–S9. MR 1197510
(94c:11005), http://dx.doi.org/10.1090/S00255718199311975103
 3.
D. H. Lehmer.
An extended theory of Lucas' functions. Annals of Mathematics, 31:419448, 1930.
 4.
E. Lucas.
Nouveaux théoremes d`arithmétique supérieure. Comptes Rendus Acad. des Sciences, Paris, 83:12861288, 1876.
 5.
H.
C. Williams, An algorithm for determining certain large
primes, and Computing (Louisiana State Univ., Baton Rouge, La., 1971)
Louisiana State Univ., Baton Rouge, La., 1971, pp. 533–556. MR 0319874
(47 #8415)
 6.
H.
C. Williams, The primality of 𝑁=2𝐴3ⁿ1,
Canad. Math. Bull. 15 (1972), 585–589. MR 0311559
(47 #121)
 7.
H.
C. Williams, The primality of certain integers of the form
2𝐴𝑟ⁿ1, Acta Arith. 39 (1981),
no. 1, 7–17. MR 638738
(84h:10012)
 8.
H.
C. Williams, A class of primality tests for trinomials which
includes the LucasLehmer test, Pacific J. Math. 98
(1982), no. 2, 477–494. MR 650024
(83f:10008)
 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
(88b:11089), http://dx.doi.org/10.1090/S0025571819870866123X
 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
 1.
 E. Bach.
Explicit bounds for primality testing and related problems. Mathematics of Computation, 55:355380, 1990. MR 91m:11096
 2.
 W. Bosma.
Explicit primality criteria for . Mathematics of Computation, 61:97109, 1993. MR 94c:11005
 3.
 D. H. Lehmer.
An extended theory of Lucas' functions. Annals of Mathematics, 31:419448, 1930.
 4.
 E. Lucas.
Nouveaux théoremes d`arithmétique supérieure. Comptes Rendus Acad. des Sciences, Paris, 83:12861288, 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. 533556. MR 47:8415
 6.
 H. C. Williams.
The primality of . Canadian Math. Bull., 15:585589, 1972. MR 47:121
 7.
 H. C. Williams.
The primality of certain integers of the form . Acta Arith., 39:717, 1981. MR 84h:10012
 8.
 H. C. Williams.
A class of primality tests for trinomials which includes the LucasLehmer test. Pacific J. Math., 98:477494, 1982. MR 83f:10008
 9.
 H. C. Williams.
Effective primality tests for some integers of the form and . Mathematics of Computation, 48:385403, 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
Similar Articles
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/S0025571800012126
PII:
S 00255718(00)012126
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
