Evaluation and comparison of two efficient probabilistic primality testing algorithms

DOI10.1016/0304-3975(80)90007-9zbMATH Open0443.10002DBLPjournals/tcs/Monier80OpenAlexW2089613796WikidataQ27940855 ScholiaQ27940855MaRDI QIDQ1144064FDOQ1144064

Authors: Louis Monier 

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90007-9

zbMATH Keywords

efficiencyalgorithmMiller-Rabin testprobabilistic primality testing

Mathematics Subject Classification ID

Distribution of primes (11N05) Primes (11A41)

Cites Work

• Title not available (Why is that?)
• Fast multiplication of large numbers
• Title not available (Why is that?)
• A Fast Monte-Carlo Test for Primality
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (29)

• On the effectiveness of a generalization of Miller's primality theorem
• Some thoughts on pseudoprimes
• Fast generation of prime numbers and secure public-key cryptographic parameters.
• Generalized strong pseudoprime tests and applications
• A probable prime test with high confidence
• The Probability that a Random Probable Prime is Composite
• The generation of random numbers that are probably prime
• Strengthening the Baillie-PSW primality test
• Prime witnesses in the Shor algorithm and the Miller-Rabin algorithm
• Finding strong pseudoprimes to several bases
• Improved error bounds for the Fermat primality test on random inputs
• Frobenius pseudoprimes
• A one-parameter quadratic-base version of the Baillie-PSW probable prime test
• Multidimensional scaling and visualization of patterns in prime numbers
• A generalization of Miller’s primality theorem
• Two kinds of strong pseudoprimes up to $10^{36}$
• The Rabin-Monier theorem for Lucas pseudoprimes
• Counting composites with two strong liars
• The Miller–Rabin test with randomized exponents
• Average liar count for degree-\(2\) Frobenius pseudoprimes
• On practical aspects of the Miller-Rabin primality test
• On the number of primality witnesses of composite integers
• An unconditional improvement to the running time of the quadratic Frobenius test
• Primality testing
• Finding strong pseudoprimes to several bases. II
• Realistic analysis of some randomized algorithms
• Pseudoprimes and Fermat numbers
• Further investigations with the strong probable prime test
• Euler pseudoprime polynomials and strong pseudoprime polynomials

This page was built for publication: Evaluation and comparison of two efficient probabilistic primality testing algorithms

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