Generalized Lucas-Lehmer tests using Pell conics (Q2845539)

The simplest primality proofs are based on the group of coprime residue classes modulo \(p\); if \(p\) is prime, this group has order \(p-1\), and if a large enough part of \(p-1\) can be factored completely, the primality of \(p\) can be established quickly. Analogous results exploiting the factorization of \(p+1\) were first established by Edouard Lucas using recurring sequences; equivalent descriptions are based on the arithmetic of quadratic number fields or the arithmetic of Pell conics. NEWLINENEWLINENEWLINEThe formulation of these primality tests using the language of Pell conics has the advantage that the tests based on the factorization of \(p-1\) and those using elliptic curves may be formulated in an analogous way. In the present article, the author shows how primality tests due to Riesel and H. C. Williams for numbers of the form \(N = m^nh \pm 1\) may be stated and proved using the arithmetic of Pell conics.