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 238. Moreover, we combined the generalized Lucas test with the Fermat test up to 264 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 / Bazzanella, Danilo; Di Scala, Antonio; Dutto, Simone; Murru, Nadir. - In: RAMANUJAN JOURNAL. - ISSN 1382-4090. - (2021). [10.1007/s11139-020-00373-9]

Primality tests, linear recurrent sequences and the Pell equation

Bazzanella, Danilo;Di Scala, Antonio;Dutto, Simone;
2021

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 238. Moreover, we combined the generalized Lucas test with the Fermat test up to 264 and we did not find any composite number that passes the test. We get the same result using the generalized Pell test.
File in questo prodotto:
File Dimensione Formato  
2002.08062.pdf

non disponibili

Descrizione: Articolo
Tipologia: 1. Preprint / submitted version [pre- review]
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 429.45 kB
Formato Adobe PDF
429.45 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Bazzanella2021_Article_PrimalityTestsLinearRecurrentS (2).pdf

non disponibili

Descrizione: articolo principale
Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 378.44 kB
Formato Adobe PDF
378.44 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
pseudo-exp-rev.pdf

Open Access dal 08/02/2022

Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: PUBBLICO - Tutti i diritti riservati
Dimensione 301.6 kB
Formato Adobe PDF
301.6 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/11583/2859494