Primality test for numbers of the form $(2p)^{2^n}+1$
Volume 169 / 2015
Acta Arithmetica 169 (2015), 301-317
MSC: Primary 11A51; Secondary 11Y11.
DOI: 10.4064/aa169-4-1
Abstract
We describe a primality test for $M=(2p)^{2^n}+1$ with an odd prime $p$ and a positive integer $n$, which are a particular type of generalized Fermat numbers. We also present special primality criteria for all odd prime numbers $p$ not exceeding $19$. All these primality tests run in deterministic polynomial time in the input size $\log_{2}M$. A special $2p$th power reciprocity law is used to deduce our result.
