The generation of random numbers that are probably prime

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

Type: Article

Publication Date: 1988-01-01

Citations: 39

DOI: https://doi.org/10.1007/bf00206325

View Publication

Download PDF

Locations

Journal of Cryptology - View - PDF

Similar Works

Action	Title	Year	Authors
+	Fast verification, testing, and generation of large primes	1979	David A. Plaisted
+	How to Generate Factored Random Numbers	1988	Eric Bach
+	Deterministic methods to find primes	2011	Terence Tao Ernest S. Croot H. A. Helfgott
+	Primality testing	2013	Joachim von zur Gathen Jürgen Gerhard
+	Close to Uniform Prime Number Generation With Fewer Random Bits	2018	Pierre-Alain Fouque Mehdi Tibouchi
+ PDF Chat	Proving primality in essentially quartic random time	2006	Daniel J. Bernstein
+ PDF Chat	Close to Uniform Prime Number Generation with Fewer Random Bits	2014	Pierre-Alain Fouque Mehdi Tibouchi
+	Deterministic methods to find primes	2010	D. H. J. Polymath
+	As opposed to prime factorization, primality testing is determining whether a given number is a prime, without necessarily computing its factorization. This lecture will study in details Solovay-Strassen algorithm for primality testing, discuss random primes generation and present one of its applications to cryptography.	2010	Baljak Valentina
+	Fast Generation of Safe Primes using Deterministic Primality Tests based on Maurer Method	2006	Kumakyu Hidehiro Niwa Akito
+	On the Classification and Algorithmic Analysis of Carmichael Numbers	2017	Sathwik Karnik
+	Random Primes without Primality Testing	2022	Pascal Giorgi Bruno Grenet Armelle Perret du Cray Daniel S. Roche
+	1. Introduction: Efficient Primality Testing	2004	Martin Dietzfelbinger
+	Prime numbers not so random?	2003	Philip Ball
+	Sharpening "Primes is in P" for a large family of numbers	2002	Pedro Berrizbeitia
+	Primality test and repeating decimal digits	2023	Simon-Pierre Blackburn
+ PDF Chat	On the Number of Witnesses in the Miller–Rabin Primality Test	2020	Shamil Ishmukhametov Bulat Gazinurovich Mubarakov R. G. Rubtsova
+	A polytime proof of correctness of the Rabin-Miller algorithm from Fermat's little theorem	2008	Grzegorz Herman Michael Soltys
+	Random primes without primality testing	2022	Pascal Giorgi Bruno Grenet Armelle Perret du Cray Daniel S. Roche
+ PDF Chat	Infinite Sets of Primes with Fast Primality Tests and Quick Generation of Large Primes	1989	J. Pintz William Steiger Endre Szemerédi

Works That Cite This (15)

Action	Title	Year	Authors
+	The least witness of a composite number	1998	R. Balasubramanian S. V. Nagaraj
+	Finding Four Million Large Random Primes	2007	Ronald L. Rivest
+	A Probable Prime Test with High Confidence	1998	Jon Grantham
+ PDF Chat	The probability that a random probable prime is composite	1989	Su Hee Kim Carl Pomerance
+	On a Deterministic Property of the Category of $k$-almost Primes: A Deterministic Structure Based on a Linear Function for Redefining the $k$-almost Primes ($\exists n\in {\rm N} $, $1{\le} k {\le}n$) in Certain Intervals	2014	Ramin Zahedi
+	Prime Number	2011	Anton Štiglić
+	Atkin’s Test: News from the Front	2007	François Morain
+ PDF Chat	Fast generation of prime numbers and secure public-key cryptographic parameters	1995	Ueli Maurer
+	On the difficulty of finding reliable witnesses	1994	W. R. Alford Andrew Granville Carl Pomerance
+ PDF Chat	Average case error estimates for the strong probable prime test	1993	Ivan Damgård Peter Landrock Carl Pomerance

Works Cited by This (11)

Action	Title	Year	Authors
+	Two Observations on Probabilistic Primality Testing	2007	Pierre Beauchemin Gilles Brassard Claude Crépeau Claude Goutier
+	On the Number of False Witnesses for a Composite Number	1986	Paul Erdös Carl Pomerance
+ PDF Chat	The pseudoprimes to 25⋅10⁹	1980	Carl Pomerance J. L. Selfridge Samuel S. Wagstaff
+	Recognizing primes in random polynomial time	1987	Leonard M. Adleman Ming-Deh A. Huang
+	The Search for Prime Numbers	1982	Carl Pomerance
+ PDF Chat	An introduction to the theory of numbers	1960	G. H. Hardy
+	Almost all primes can be quickly certified	1986	S. Goldwasser Joe Kilian
+	On Distinguishing Prime Numbers from Composite Numbers	1983	Leonard M. Adleman Carl Pomerance Robert Rumely
+	An Introduction to the Theory of Numbers. By G. H. Hardy and E. M. Wright. 2nd edition. Pp. xvi, 407 25s. 1945. (Oxford)	1946	T. A. A. B.
+ PDF Chat	Lucas pseudoprimes	1980	Robert Baillie Samuel S. Wagstaff