Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Explicit primality criteria for $(p-1)\,p^n-1$

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

Abstract | References | Similar Articles | Additional Information


Deterministic polynomial time primality criteria for $2^n-1$ 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 $N_n=(p-1)\,p^n-1$, where $p$ is any fixed prime. When $n>(p-1)/2$ we show that it is always possible to produce a Lucas-like deterministic test for the primality of $N_n$ which requires that only $O(q\,(p+\log q)+p^3+\log N_n)$ modular multiplications be performed modulo $N_n$, as long as we can find a prime $q$ of the form $1+k\, p$ such that $N_n^{\,k}-1$ is not divisible by $q$. We also show that for all $p$ with $3<p<10^7$ such a $q$ can be found very readily, and that the most difficult case in which to find a $q$ appears, somewhat surprisingly, to be that for $p=3$. Some explanation is provided as to why this case is so difficult.

References [Enhancements On Off] (What's this?)

  • 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 $h\cdot2^k\pm1$.
    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 $2 A 3^n-1$.
    Canadian Math. Bull., 15:585-589, 1972. MR 47:121
  • 7. H. C. Williams.
    The primality of certain integers of the form $2 A r^n-1$.
    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 $A 5^n-1$ and $A 7^n-1$.
    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

Similar Articles

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

H. C. Williams
Affiliation: University of Manitoba, Department of Computer Science, Winnipeg, Manitoba, Canada R3T 2N2

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

American Mathematical Society