  In this paper we generalize the classical Proth's theorem for integers of the
form $N=Kp^n+1$. For these families, we present a primality test whose
computational complexity is $\widetilde{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.
