On the effectiveness of a generalization of Miller's primality theorem

DOI10.1016/j.jco.2010.01.002zbMath1258.11101OpenAlexW1964871538MaRDI QIDQ964923

Zhenxiang Zhang

Publication date: 21 April 2010

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2010.01.002

zbMATH Keywords

complexity analysiscompositeness detectingprimality proving under the ERHstrong probable prime (sprp) teststhe Berrizbeitia-Olivieri primality testthe Miller primality test

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Factorization; primality (11A51) Primality (11Y11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic algorithm for testing primality
• Evaluation and comparison of two efficient probabilistic primality testing algorithms
• Riemann's hypothesis and tests for primality
• There are infinitely many Carmichael numbers
• Generalized strong pseudoprime tests and applications
• PRIMES is in P
• Finding strong pseudoprimes to several bases
• Average Case Error Estimates for the Strong Probable Prime Test
• A one-parameter quadratic-base version of the Baillie-PSW probable prime test
• Explicit Bounds for Primality Testing and Related Problems
• A generalization of Miller’s primality theorem
• Two kinds of strong pseudoprimes up to $10^{36}$
• The Pseudoprimes to 25 ⋅10 9
• Lucas Pseudoprimes
• On Strong Pseudoprimes to Several Bases
• Finding strong pseudoprimes to several bases. II
• Some new kinds of pseudoprimes
• Finding 𝐶₃-strong pseudoprimes
• Notes on some new kinds of pseudoprimes

This page was built for publication: On the effectiveness of a generalization of Miller's primality theorem