### Close to Uniform Prime Number Generation With Fewer Random Bits

Pierre-Alain Fouque and Mehdi Tibouchi

##### Abstract

In this paper we analyze a simple method for generating prime numbers with fewer random bits. Assuming the Extended Riemann Hypothesis, we can prove that our method generates primes according to a distribution that can be made arbitrarily close to uniform. This is unlike the PRIMEINC algorithm studied by Brandt and Damg\aa{a}rd and its many variants implemented in numerous software packages, which reduce the number of random bits used at the price of a distribution easily distinguished from uniform. Our new method is also no more computationally expensive than the ones in current use, and opens up interesting options for prime number generation in constrained environments.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Keywords
Prime number generationRSAefficient implementationsrandom bits
Contact author(s)
mehdi tibouchi @ normalesup org
History
Short URL
https://ia.cr/2011/481

CC BY

BibTeX

@misc{cryptoeprint:2011/481,
author = {Pierre-Alain Fouque and Mehdi Tibouchi},
title = {Close to Uniform Prime Number Generation With Fewer Random Bits},
howpublished = {Cryptology ePrint Archive, Paper 2011/481},
year = {2011},
note = {\url{https://eprint.iacr.org/2011/481}},
url = {https://eprint.iacr.org/2011/481}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.