Close to Uniform Prime Number Generation with Fewer Random Bits

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 q ∝ x 1−ε , pick a uniformly random a < q coprime to q, and choose p of the form a + t · q, 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. 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. In particular: – it uses much fewer random bits than both the "trivial algorithm" (testing random numbers less than x for primality) and Maurer's almost uniform prime generation algorithm; – the distance of its output distribution to uniform can be made arbitrarily small, unlike algorithms like PRIMEINC (studied by Brandt and Damgård), which we show exhibit significant biases; – all quality measures (number of primality tests, output entropy, randomness, etc.) can be obtained under very standard conjectures or even unconditionally, whereas most previous nontrivial algorithms can only be proved based on stronger, less standard assumptions like the Hardy–Littlewood prime tuple conjecture.
Type de document :
Communication dans un congrès
Javier Esparza; Pierre Fraigniaud; Thore Husfeldt; Elias Koutsoupias. ICALP 2014 - 41st International Colloquium on Automata, Languages and Programming, Jul 2014, Copenhague, Denmark. Springer, LNCS 8572, pp.11, 2014, ICALP 2014. 〈10.1007/978-3-662-43948-7_82〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01094062
Contributeur : Pierre-Alain Fouque <>
Soumis le : jeudi 11 décembre 2014 - 15:46:37
Dernière modification le : mercredi 16 mai 2018 - 11:23:29
Document(s) archivé(s) le : jeudi 12 mars 2015 - 10:56:12

Fichier

1406.7078v1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre-Alain Fouque, Mehdi Tibouchi. Close to Uniform Prime Number Generation with Fewer Random Bits. Javier Esparza; Pierre Fraigniaud; Thore Husfeldt; Elias Koutsoupias. ICALP 2014 - 41st International Colloquium on Automata, Languages and Programming, Jul 2014, Copenhague, Denmark. Springer, LNCS 8572, pp.11, 2014, ICALP 2014. 〈10.1007/978-3-662-43948-7_82〉. 〈hal-01094062〉

Partager

Métriques

Consultations de la notice

30

Téléchargements de fichiers

46