Random primes in arithmetic progressions

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

Paper 2022/160

Random primes in arithmetic progressions

Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray, and 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. MINOR revision.
Keywords: prime numbers multiplicative subgroups
Contact author(s): roche @ usna edu
History: 2022-02-12: received
Short URL: https://ia.cr/2022/160
License: CC BY

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}
}