We study new primality tests based on linear recurrent sequences of degree two exploiting a matrix approach. The classical Lucas test arises as a particular case and we see how it can be easily improved. Moreover, this approach shows clearly how the Lucas pseudoprimes are connected to the Pell equation and the Brahamagupta product. We also introduce two new specific primality tests, which we will call generalized Lucas test and generalized Pell test. We perform some numerical computations on the new primality tests and we do not find any pseudoprime up to 2 38. Moreover, we combined the generalized Lucas test with the Fermat test up to 2 64 and we did not find any composite number that passes the test. We get the same result using the generalized Pell test.

Primality tests, linear recurrent sequences and the Pell equation

Murru N.
2021-01-01

Abstract

We study new primality tests based on linear recurrent sequences of degree two exploiting a matrix approach. The classical Lucas test arises as a particular case and we see how it can be easily improved. Moreover, this approach shows clearly how the Lucas pseudoprimes are connected to the Pell equation and the Brahamagupta product. We also introduce two new specific primality tests, which we will call generalized Lucas test and generalized Pell test. We perform some numerical computations on the new primality tests and we do not find any pseudoprime up to 2 38. Moreover, we combined the generalized Lucas test with the Fermat test up to 2 64 and we did not find any composite number that passes the test. We get the same result using the generalized Pell test.
2021
1
14
Linear recurrent sequence; Lucas pseudoprime; Pell equation; Pell pseudoprime; Primality test
Bazzanella D.; Scala A.D.; Dutto S.; Murru N.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1796619
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact