Primality test for numbers of the form \(A p^n + w_n\) (Q491620)

In this article, the authors generalize classical primality tests such as those by Lucas-Lehmer and Proth. These new tests apply to numbers of the form \(M = Ap^n + w_n\), where \(w_n^{p-1} \equiv 1 \bmod p^n\) and \(A < p^n\). The authors construct integers \(U^{(m)}\) and sequences \(T_k^{(m)}\) of rational numbers for \(m = 1, \ldots, \frac{p-1}2\) as explicitly given symmetric polynomials of certain elements in the field of \(p\)-th roots of unity; for finding these elements, Eisenstein's reciprocity law is used. The main result is that \(M\) is prime if and only if the congruences \(T_{n-1}^{(m)} \equiv U^{(m)} \bmod M\) hold for each \(m\) with \(1 \leq m \leq \frac{p-1}2\).