Home
Search Site
Largest
Finding
How Many?
Mersenne
Glossary
Prime Curios!
email list
FAQ
Prime Lists
Titans
Submit primes

This is the Prime Pages'
interface to our BibTeX database. Rather than being an exhaustive database,
it just lists the references we cite on these pages. Please let me know of any errors you notice.References: [ Home  Author index  Key index  Search ]
 SW2000
 A. Stein and H. C. Williams, "Explicit primality criteria for (p1) p^{n}1," Math. Comp., 69 (2000) 17211734. MR 2001j:11124
Abstract:
Deterministic polynomial time primality criteria for 2^{n}1 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 N_{n}=(p1) p^{n}1, where p is any fixed prime. When n>(p1)/2 we show that it is always possible to produce a Lucaslike 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.
