A faster pseudo-primality test
Langue
en
Article de revue
Ce document a été publié dans
Rendiconti del Circolo Matematico di Palermo. 2012-08, vol. 61, n° 2, p. 261-278
Springer-Verlag Italia
Résumé en anglais
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 en anglais
Probabilistic algorithms
Primality
Ring theory
Galois theory