Primality testing with fewer random bits

DOI10.1007/BF01275488zbMath0791.11071OpenAlexW2025184368WikidataQ62472242 ScholiaQ62472242MaRDI QIDQ1321031

Victor Shoup, René Peralta

Publication date: 8 May 1994

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

Full work available at URL: https://doi.org/10.1007/bf01275488

zbMATH Keywords

randomized algorithmsderandomizationerror probabilitiesMiller-Rabin testprimality testing algorithmsSolovay-Strassen test

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Primality (11Y11)

Cites Work

• Unnamed Item
• Unnamed Item
• Factoring polynomials using fewer random bits
• Probabilistic algorithm for testing primality
• Riemann's hypothesis and tests for primality
• Realistic analysis of some randomized algorithms
• Randomized algorithms and pseudorandom numbers
• A Fast Monte-Carlo Test for Primality