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

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.