A faster pseudo-primality test
COUVEIGNES, Jean-Marc
Institut de Mathématiques de Bordeaux [IMB]
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Institut de Mathématiques de Bordeaux [IMB]
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
COUVEIGNES, Jean-Marc
Institut de Mathématiques de Bordeaux [IMB]
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
< Reduce
Institut de Mathématiques de Bordeaux [IMB]
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Language
en
Article de revue
This item was published in
Rendiconti del Circolo Matematico di Palermo. 2012-08, vol. 61, n° 2, p. 261-278
Springer-Verlag Italia
English Abstract
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.
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.Read less <
English Keywords
Probabilistic algorithms
Primality
Ring theory
Galois theory
Origin
Hal imported