A faster pseudo-primality test
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Fast Modular Composition in any Characteristic2008
- Proving primality in essentially quartic random timeMathematics of Computation, 2006
- PRIMES is in PAnnals of Mathematics, 2004
- Fast Construction of Irreducible Polynomials over Finite FieldsJournal of Symbolic Computation, 1994
- On Distinguishing Prime Numbers from Composite NumbersAnnals of Mathematics, 1983
- On Ramification Theory in Noetherian RingsAmerican Journal of Mathematics, 1959