Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

Abstract:

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
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
PII: S 0025-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