Effective Primality Test for p2ⁿ+1, p prime, n>1

2018/11/14 by Tejas Rao, Rao, Tejas R.
Mathematics · Computer Science · #Analytic Number Theory Research #Cryptography and Residue Arithmetic #History and Theory of Mathematics

paper · pdf · doi:10.48550/arxiv.1811.06070

Abstract

We develop a simple O((log n)²) test as an extension of Proth's test for the primality for p2ⁿ+1, p>2ⁿ. This allows for the determination of large, non-Sierpinski primes p and the smallest n such that p2ⁿ+1 is prime. If p is a non-Sierpinski prime, then for all n where p2ⁿ+1 passes the initial test, p2ⁿ+1 is prime with 3 as a primitive root or is primover and divides the base 3 Fermat Number, GF(3,n-1). We determine the form the factors of any composite overpseudoprime that passes the initial test take by determining the form that factors of GF(3,n-1) take.

Related

• A primality test for Kpⁿ+1 numbers
• A primality test for Kpⁿ+1 numbers and a generalization of Safe Primes and Sophie Germain Primes
• Primality test for numbers of the form (2p)²ⁿ+1
• Primality tests for specific classes of N=k⋅ 2^m ± 1
• Primality tests for Fermat numbers and 2^(2k+1)±2^(k+1)+1