Developments on primality tests based on linear recurrent sequences of degree two

Some probabilistic primality tests, like the strong Lucas test that is part of the widely used Baillie-PSW test, are defined through linear recurrent sequences. When adopting linear recurrent sequences of degree two, the simple version of the Lucas test as well as tests based on the Pell hyperbola can be generalized obtaining new powerful primality tests. This paper describes a deeper analysis of these two generalized tests in order to find the best parameters by number of pseudoprimes, i.e., the instances of the tests with less composite integers that are declared primes. The Selfridge method for choosing the parameters of the Lucas test can be adapted to the generalized tests and, when adopting the parameters among those with best statistical results, the resulting tests have no pseudoprimes up to 2