A faster pseudo-primality test

Abstract

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

Published in Rendiconti del Circolo Matematico di Palermo Journal, Springer

References in corpus (2)

• Powers of Tensors and Fast Matrix Multiplication
• Computing separable isogenies in quasi-optimal time