Explicit primality criteria for (p-1)p(n)-1

Deterministic polynomial time primality criteria for 2(n) -1 have been know n 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. Wh en 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 module N- n as long as we can find a prime q of the form 1 + kappa p such that N-n(ka ppa) - 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. So me explanation is provided as to why this case is so difficult.