{"id":"arxiv/2609.25393","url":"https://arxiv.org/abs/2609.25393","tags":["math.NT","cs.DS","math.GR"],"score":0,"title":"On the generation of multiplicative groups by small primes","domain":"math.NT","source":"arxiv","authors":["Oleksiy Klurman","Igor E. Shparlinski","Joni Teräväinen"],"reviews":0,"subject":"math.NT","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-21","reactions":{}}