A primality test for š¾šāæ+1 numbers
J. M. Grau, Antonio M. OllerāMarcĆ©n, Daniel Sadornil Ā· Mathematics of Computation Ā· 2014
In this paper we generalize the classical Prothās theorem and the Miller-Rabin test for integers of the form N = K p n + 1 N=Kp^n+1 . For these families, we present variations on the classical Pocklingtonās results and, in particular, a primality test whose computational complexity is O ~ ( log 2 ā” N ) \widetilde {O}(\log ^2 N) and, what is more important, that requires only one modular exponentiation modulo N N similar to that of Fermatās test.