A faster pseudo-primality test
Jean-Marc Couveignes, Tony Ezome, Lercier, Reynald · arXiv (Cornell University) · 2012
We propose a pseudo-primality test using cyclic extensions of $\mathbb Z/n \mathbb Z$. For every positive integer $k \leq \log n$, this test achieves the security of $k$ Miller-Rabin tests at the cost of $k^{1/2+o(1)}$ Miller-Rabin tests.