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 Free Access

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?)

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

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