A primality test for $K{p}^n+1$ numbers

Abstract

In this paper we generalize the classical Proth's theorem for integers of the form $N=K{p}^n+1$. For these families, we present a primality test whose computational complexity is $\tilde{O}({\log }^2(N))$ and, what is more important, that requires only one modular exponentiation similar to that of Fermat's test. Consequently, the presented test improves the most often used one, derived from Pocklington's theorem, which usually requires the computation of several modular exponentiations together with some GCD's.