  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.
