Primality tests, linear recurrent sequences and the Pell equation (Q2075076)

The celebrated Lucas primality test is based on properties of the Lucas sequence \(\{U_k\}\)\, with \(U_0=0,\, U_1=1\)\, and \(U_k=PU_{k-1}+QU_{k-2};\, k\ge 2,\, P,Q \in \mathbb{Z}\). This test is equivalent to a Pell test based on the Pell equation \(x^2-Dy^2=1,\, D=P^2-4Q\), see [\textit{A. J. Di Scala} et al ., ``Lucas pseudoprimes and the Pell conic'', Preprint, \url{arxiv:2001.00353}]. The Lucas test has been generalized by many authors using other linear recurrence sequences. The present paper follows these paths and proposes two primality tests, that the authors call generalized Lucas test and generalized Pell test and it defines the corresponding pseudoprimes. Section 2 studies primality tests based on linear recurrent sequences defined by matrices \(M\in \mathbb{Z}^{2 \times 2}\). Lucas and Pell tests are then particular cases of this approach. Section 3 shows the results of numerical experiments with these primality tests and the comparison of their performances for different values of the parameters and then the Selfridge method is used for finding good parameters (see Figures 1,2,3 and Table 1). In particular with those generalized tests the authors do not find any pseudoprimes up to \(2^{38}\).