Effective Primality Test for $p{2}^n+1$, $p$ prime, $n>1$

Abstract

We develop a simple $O((\log n{)}^2)$ test as an extension of Proth's test for the primality for $p{2}^n+1$, $p>2^n$. This allows for the determination of large, non-Sierpinski primes $p$ and the smallest $n$ such that $p{2}^n+1$ is prime. If $p$ is a non-Sierpinski prime, then for all $n$ where $p{2}^n+1$ passes the initial test, $p{2}^n+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.

3 pages