A faster pseudo-primality test

Jean-Marc Couveignes (1, 2, 3) , Tony Ezome (4) , Reynald Lercier (5)

1 IMB - Institut de Mathématiques de Bordeaux
2 LFANT - Lithe and fast algorithmic number theory
3 LIRIMA - Laboratoire International de Recherche en Informatique et Mathématiques Appliquées
4 USTM - Université des Sciences et Techniques de Masuku
5 IRMAR - Institut de Recherche Mathématique de Rennes

We propose a pseudo-primality test using cyclic extensions of $Z/nZ$. For every positive integer $k$ this test achieves the security of $k^2$ Miller-Rabin tests at the cost of $k^{1+o(1)}$ Miller-Rabin tests.

Mots clés: Probabilistic algorithms; Primality; Ring theory; Galois theory

Domaines: Théorie des nombres [math.NT]

Jean-Marc Couveignes, Tony Ezome, Reynald Lercier. A faster pseudo-primality test. Rendiconti del Circolo Matematico di Palermo, 2012, 61 (2), pp.261-278. ⟨10.1007/s12215-012-0088-0⟩. ⟨hal-00694113⟩