References: [ Home | Author index | Key index | Search ]

SW2000

A. Stein and H. C. Williams, "Explicit primality criteria for (p-1) pⁿ-1," Math. Comp., 69 (2000) 1721--1734.  MR 2001j:11124

Abstract: Deterministic polynomial time primality criteria for 2ⁿ-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ⁿ-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³+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⁷ 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.