Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 56 min ago
PreprintarXiv licencearXiv

On the generation of multiplicative groups by small primes

  • Oleksiy Klurman
  • Igor E. Shparlinski
  • Joni Teräväinen
Open at sourcePDFDOICite

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 (ℤ/qℤ)× 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 (log Q)1+ε 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 ε and A) integers q≤ Q, every element of (ℤ/qℤ)× 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.

Related

  1. Few small primes suffice to cover unit groups
    Scott D. Hughes
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  2. Galois groups of Apéry-like series modulo primes
    Xavier Caruso, Florian Fürnsinn, Daniel Vargas Montoya +1
    Bulletin of the Australian Mathematical SocietyPeer-reviewedLicence not statedAlgebra & number theoryCombinatorics & discrete mathematicsHAL
  3. Non-vanishing mod p of derived Hecke algebras of multiplicative groups over number fields, II
    Jaesung Kwon
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  4. On a Turán's theorem for small primes
    T. Makoto Minamide, Haruka Sakai, Yoshio Tanigawa
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  5. Cohomology and multiplicative gaps for quasi-isometries of nilpotent groups
    Mayukh Mukherjee, Soumyadeb Samanta, Soumyadip Thandar
    arXivPreprintarXiv licenceFull textAlgebra & number theoryGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{klurman2026generation,
  title = {{On the generation of multiplicative groups by small primes}},
  author = {Oleksiy Klurman and Igor E. Shparlinski and Joni Teräväinen},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.25393},
  eprint = {2609.25393},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.25393},
}
RIS
TY  - UNPB
TI  - On the generation of multiplicative groups by small primes
AU  - Oleksiy Klurman
AU  - Igor E. Shparlinski
AU  - Joni Teräväinen
PY  - 2026
DA  - 2026/09/21
PB  - arXiv
DO  - 10.48550/arxiv.2609.25393
UR  - https://arxiv.org/abs/2609.25393
AB  - 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 (ℤ/qℤ)^× 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 (log Q)^1+ε 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 ε and A) integers q≤ Q, every element of (ℤ/qℤ)^× 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.
ER  -