A faster pseudo-primality test

DOI10.1007/S12215-012-0088-0MaRDI QIDQ1758643zbMATH OpenOpenAlexFDO

Authors Jean-Marc Couveignes, Tony Ezome

Publication date 15 November 2012

Published in Rendiconti del Circolo Matematico di Palermo (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.1657

zbMATH Keywords

Miller-Rabin testprobabilistic algorithmsprimalityGalois theory.

Mathematics Subject Classification ID

Factorization; primality (11A51) Primality (11Y11) Galois theory and commutative ring extensions (13B05)

Abstract: We propose a pseudo-primality test using cyclic extensions of $mathbbZ/nmathbbZ$. For every positive integer $kleqlogn$, this test achieves the security of $k$ Miller-Rabin tests at the cost of $k^{1/2+o(1)}$ Miller-Rabin tests.

Recommendations

• Generalized strong pseudoprime tests and applications
• Four primality testing algorithms
• Rabin-Miller Primality Test: Composite Numbers Which Pass It
• scientific article; zbMATH DE number 1954367
• Primality testing using elliptic curves
• scientific article; zbMATH DE number 721898
• A probable prime test with very high confidence for \(n \equiv 3\mod4\)
• scientific article; zbMATH DE number 1588470
• Recent developments in primality proving
• Publication:4204199

Cites work

• scientific article; zbMATH DE number 3747230 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1954367 (Why is no real title available?)
• scientific article; zbMATH DE number 3230409 (Why is no real title available?)
• scientific article; zbMATH DE number 3394444 (Why is no real title available?)
• Fast construction of irreducible polynomials over finite fields
• Four primality testing algorithms
• On Ramification Theory in Noetherian Rings
• On distinguishing prime numbers from composite numbers
• PRIMES is in P
• Primality Testing and Jacobi Sums
• Proving primality in essentially quartic random time
• Riemann's hypothesis and tests for primality
• Separable algebras over commutative rings

Cited in

(10)

• Fast Primality Tests for Numbers Less Than 50 ⋅10 9
• A Performance Analysis of a Simple Prime-Testing Algorithm
• Bad witnesses for a composite number
• scientific article; zbMATH DE number 5845877 (Why is no real title available?)
• Fast computation of elliptic curve isogenies in characteristic two
• scientific article; zbMATH DE number 1954367 (Why is no real title available?)
• scientific article; zbMATH DE number 3910467 (Why is no real title available?)
• Public Key Cryptography - PKC 2005
• A Fast Monte-Carlo Test for Primality
• scientific article; zbMATH DE number 962546 (Why is no real title available?)

This page was built for publication: A faster pseudo-primality test

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1758643)