Random primes in arithmetic progressions

Pascal Giorgi; Bruno Grenet; Armelle Perret du Cray; Daniel S.  Roche

Paper 2022/160 Original: eprint.iacr.org/2022/160 ↗

Random primes in arithmetic progressions

Pascal Giorgi

Bruno Grenet

Armelle Perret du Cray

Daniel S. Roche

Abstract

We describe a straightforward method to generate a random prime q such that the multiplicative group GF(q)* also has a random large prime-order subgroup. The described algorithm also yields this order p as well as a p'th primitive root of unity. The methods here are efficient asymptotically, but due to large constants may not be very useful in practical settings.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
History: 2022-02-12: last updated; 2022-02-12: published
Short URL: https://ia.cr/2022/160
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2022/160,
      author = {Pascal Giorgi and Bruno Grenet and Armelle Perret du Cray and Daniel S.  Roche},
      title = {Random primes in arithmetic progressions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/160},
      year = {2022},
      url = {https://eprint.iacr.org/2022/160}
}