A faster pseudo-primality test

DOI10.1007/S12215-012-0088-0zbMATH Open1257.11106arXiv1204.1657OpenAlexW3105336851MaRDI QIDQ1758643FDOQ1758643

Authors: Jean-Marc Couveignes, Tony Ezome 

Publication date: 15 November 2012

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

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.

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

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

zbMATH Keywords

Miller-Rabin testprobabilistic algorithmsprimalityGalois theory.

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On distinguishing prime numbers from composite numbers
• Riemann's hypothesis and tests for primality
• PRIMES is in P
• Title not available (Why is that?)
• Four primality testing algorithms
• Separable algebras over commutative rings
• Fast construction of irreducible polynomials over finite fields
• On Ramification Theory in Noetherian Rings
• Title not available (Why is that?)
• Proving primality in essentially quartic random time
• Primality Testing and Jacobi Sums
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

• Title not available (Why is that?)
• Fast Primality Tests for Numbers Less Than 50 ⋅10 9
• Bad witnesses for a composite number
• Title not available (Why is that?)
• Title not available (Why is that?)
• Public Key Cryptography - PKC 2005
• A Performance Analysis of a Simple Prime-Testing Algorithm
• Title not available (Why is that?)
• Fast computation of elliptic curve isogenies in characteristic two
• A Fast Monte-Carlo Test for Primality

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)