On the generation of multiplicative groups by small primes

Oleksiy Klurman; Igor E. Shparlinski; Joni Ter\"av\"ainen

In the authors' words

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 $(Z / q Z)^{\times}$ when each prime may be used with exponent only $0$ or $1$ . We prove that, for every fixed $ε > 0$ and $A > 0$ , there is an absolute constant $C_{*}$ and a set of at most $(lo g Q)^{1 + ε}$ primes, all at most $(lo g Q)^{C_{*} (A + 1)}$ , such that for all but $O (Q (lo g Q)^{- A})$ (with the implied constant depending only on $ε$ and $A$ ) integers $q \leq Q$ , every element of $(Z / q Z)^{\times}$ is a product of a subset of these primes modulo $q$ . The exponent $1 + ε$ in the number of primes is best possible up to the arbitrary $ε$ in the exponent.

Main resultLimitation the authors admit

On the generation of multiplicative groups by small primes

In the authors' words

More on Algebra & number theory that day

The Odlyzko-Poonen Conjecture on Irreducibility of Random Polynomials

Solution to Dixmier's Problem about spectra of C*-algebras

Poincar\'e Duality and Quadratic Refinements over Laurent Rings

On Haagerup-Izumi fusion categories

Monoidal Gr\"obner systems and categories of affine Brauer type