The generation of random numbers that are probably prime

DOI10.1007/BF00206325zbMath0669.10014MaRDI QIDQ1118632

Claude Crépeau, Gilles Brassard, Pierre Beauchemin, Claude Goutier, Carl B. Pomerance

Publication date: 1988

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

zbMATH Keywords

false witnessesFermat's testgeneration of random primesRabin's probabilistic primality testrandom probable prime numbers

Mathematics Subject Classification ID

Cryptography (94A60) Random number generation in numerical analysis (65C10) Primality (11Y11)

Related Items

Improved error bounds for the Fermat primality test on random inputs, Fast generation of prime numbers and secure public-key cryptographic parameters., The Probability that a Random Probable Prime is Composite, Further investigations with the strong probable prime test, Elliptic Curves and Primality Proving, Prime-number algorithm for public-key systems, A probable prime test with high confidence

Cites Work

• On distinguishing prime numbers from composite numbers
• Probabilistic algorithm for testing primality
• Evaluation and comparison of two efficient probabilistic primality testing algorithms
• Riemann's hypothesis and tests for primality
• On the Number of False Witnesses for a Composite Number
• Implementation of a new primality test
• The Pseudoprimes to 25 ⋅10 9
• Lucas Pseudoprimes
• Every Prime Has a Succinct Certificate
• A Fast Monte-Carlo Test for Primality
• Computational Complexity of Probabilistic Turing Machines
• A method for obtaining digital signatures and public-key cryptosystems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item