arXiv preprint ·
On the generation of multiplicative groups by small primes
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Number Theory
Sample Complexity of Equivariant Reinforcement Learning
Algorithms for Finite Group Epimorphism Testing
Quantum Algorithms for Minimum Generating Set
CAS II: Orbits as Models: Kolmogorov's Structure Function under Symmetry
Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2
Get the few papers worth your time in Number Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.