Close to uniform prime number generation with fewer random bits

DOI10.1007/978-3-662-43948-7_82zbMATH Open1414.11165arXiv1406.7078OpenAlexW31244460MaRDI QIDQ5167809FDOQ5167809

Authors: Pierre-Alain Fouque, Mehdi Tibouchi 

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: In this paper, we analyze several variants of a simple method for generating prime numbers with fewer random bits. To generate a prime $p$ less than $x$, the basic idea is to fix a constant $qpropto{x}^{1-varepsilon}$, pick a uniformly random $a<q$ coprime to $q$, and choose $p$ of the form $a+tcdotq$, where only $t$ is updated if the primality test fails. We prove that variants of this approach provide prime generation algorithms requiring few random bits and whose output distribution is close to uniform, under less and less expensive assumptions: first a relatively strong conjecture by H.L. Montgomery, made precise by Friedlander and Granville; then the Extended Riemann Hypothesis; and finally fully unconditionally using the Barban-Davenport-Halberstam theorem. We argue that this approach has a number of desirable properties compared to previous algorithms.

Full work available at URL: https://arxiv.org/abs/1406.7078

Recommendations

• scientific article; zbMATH DE number 697832
• scientific article; zbMATH DE number 1759305
• scientific article; zbMATH DE number 708818
• How to Generate Factored Random Numbers
• Fast generation of prime numbers and secure public-key cryptographic parameters.

zbMATH Keywords

cryptographynumber theoryprime number generation

Mathematics Subject Classification ID

Cryptography (94A60) Combinatorial probability (60C05) Number-theoretic algorithms; complexity (11Y16) Primality (11Y11)

Cited In (3)

• Generating random factored numbers, easily
• Zero-knowledge proofs for set membership: efficient, succinct, modular
• Zero-knowledge proofs for set membership: efficient, succinct, modular

This page was built for publication: Close to uniform prime number generation with fewer random bits

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