Primality Test for Numbers of the Form Ap^n+w

Abstract

We propose an algorithm determining the primality of numbers $M=A{p}^n+w_n$ where $w_n^{p-1}\equiv 1(\mathrm{mod}{p}^n)$ and $A<p^n$ and give example when $p=7$. $p$ th reciprocity law is involved. The algorithm runs in polynomial time in ${\log }_2(M)$ for fixed $p$ and $A$.