A primality test for Kpⁿ+1 numbers

2010/11/22 by José María Grau, Grau, José María, Antonio M. Oller-Marcén +1
Mathematics · #11A51 #11B99 #11Y11 #11Y16 #FOS: Mathematics #Number Theory (math.NT) #math.NT #msc:11A51 #msc:11B99 #msc:11Y11 #msc:11Y16

paper · pdf · doi:10.48550/arxiv.1011.4836

arxiv created 2011/04/26 · arxiv updated 2011/04/27

Abstract

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

Related

• A primality test for Kpⁿ+1 numbers and a generalization of Safe Primes and Sophie Germain Primes
• Primality tests for Fermat numbers and 2^(2k+1)±2^(k+1)+1
• Primality tests for specific classes of N=k⋅ 2^m ± 1
• Effective Primality Test for p2ⁿ+1, p prime, n>1
• Relaxing the size constraints on the criterion of Proth