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 ]
- A. Stein and H. C. Williams, "Explicit primality criteria for (p-1) pn-1," Math. Comp., 69 (2000) 1721--1734. MR 2001j:11124
Deterministic polynomial time primality criteria for 2n-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 Nn=(p-1) pn-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 Nn which requires that only O(q (p+log q)+p3+log Nn) modular multiplications be performed modulo Nn, as long as we can find a prime q of the form 1+k p such that Nnk-1 is not divisible by q. We also show that for all p with 3<p<107 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.