Primality testing with fewer random bits

DOI10.1007/BF01275488MaRDI QIDQ1321031zbMATH OpenOpenAlexDBLPWikidataFDO

Authors René Peralta, Victor Shoup

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

derandomizationerror probabilitiesMiller-Rabin testprimality testing algorithmsrandomized algorithmsSolovay-Strassen test

Mathematics Subject Classification ID

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

Recommendations

• Average Case Error Estimates for the Strong Probable Prime Test
• The error probability of the Miller-Rabin primality test
• scientific article; zbMATH DE number 721898

Cites work

• A Fast Monte-Carlo Test for Primality
• Factoring polynomials using fewer random bits
• scientific article; zbMATH DE number 3882549 (Why is no real title available?)
• scientific article; zbMATH DE number 3032896 (Why is no real title available?)
• Probabilistic algorithm for testing primality
• Randomized algorithms and pseudorandom numbers
• Realistic analysis of some randomized algorithms
• Riemann's hypothesis and tests for primality

Cited in

(18)

• The error probability of the Miller-Rabin primality test
• On the number of primality witnesses of composite integers
• Realistic analysis of some randomized algorithms
• On practical aspects of the Miller-Rabin primality test
• Average Case Error Estimates for the Strong Probable Prime Test
• Experimental results on probable primality
• Randomized compositeness testing with Chebyshev polynomials
• A Fast Monte-Carlo Test for Primality
• A note on monte carlo primality tests and algorithmic information theory
• scientific article; zbMATH DE number 579167 (Why is no real title available?)
• scientific article; zbMATH DE number 721898 (Why is no real title available?)
• scientific article; zbMATH DE number 2081060 (Why is no real title available?)
• scientific article; zbMATH DE number 1857655 (Why is no real title available?)
• An extended quadratic Frobenius primality test with average and worst case error estimates.
• Average Case Error Estimates of the Strong Lucas Test
• An extended quadratic Frobenius primality test with average- and worst-case error estimate
• On the effectiveness of a generalization of Miller's primality theorem
• A low complexity probabilistic test for integer multiplication

This page was built for publication: Primality testing with fewer random bits

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