Abstract: In this paper we generalize the classical Proth’s theorem and the Miller-Rabin test for integers of the form N = Kpn +1. For these families, we present variations on the classical Pocklington’s results and, in particular, a primality test whose computational complexity is  O(log2 N) and, what is more important, that requires only one modular exponentiation modulo N similar to that of Fermat’s test

Authorship

Download reference