Small sets of primes generate large multiplicative groups efficiently
On the generation of multiplicative groups by small primes
Data Structures and Algorithms
Summary
This paper studies how a group of numbers formed by all the numbers less than a number q that are relatively prime to q (called the multiplicative group modulo q) can be built using only a few small prime numbers multiplied together. The authors found that for most numbers q up to a large value Q, you only need a small number of such primes to generate every element of these groups, with each prime used at most once. Their work answers a question inspired by quantum computing algorithms for factoring numbers. They also show that the number of primes needed is close to the smallest possible.
What this means in practice
- •For cryptography engineers: Optimize certain modular arithmetic operations by understanding minimal prime generators relevant to cryptographic algorithms.
- •For quantum algorithm developers: Inform improvements in quantum factoring algorithms by clarifying the prime sets underlying group generation constraints.
A theory result. No direct application yet.
Authors
Oleksiy Klurman, Igor E. Shparlinski, Joni Teräväinen
Abstract
Motivated by a question of Regev arising from his improved quantum factoring algorithm, we study how many small primes are needed to generate the group $({\mathbb Z}/q{\mathbb Z})^\times$ when each prime may be used with exponent only $0$ or $1$. We prove that, for every fixed $\varepsilon>0$ and $A>0$, there is an absolute constant $C_*$ and a set of at most $(\log Q)^{1+\varepsilon}$ primes, all at most $(\log Q)^{C_*(A+1)}$, such that for all but $O(Q(\log Q)^{-A})$ (with the implied constant depending only on $\varepsilon$ and $A$) integers $q\leq Q$, every element of $({\mathbb Z}/q{\mathbb Z})^\times$ is a product of a subset of these primes modulo $q$. The exponent $1+\varepsilon$ in the number of primes is best possible up to the arbitrary $\varepsilon$ in the exponent.