Distribution of elements of cosets of small subgroups and applications

DOI10.1093/IMRN/RNR097MaRDI QIDQ2888915zbMATH OpenOpenAlexFDO

Authors Jean Bourgain, Sergei Konyagin, Igor E. Shparlinski

Publication date 4 June 2012

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.0296

zbMATH Keywords

discrete logarithmmultiplicative subgroupsuniform distribution

Mathematics Subject Classification ID

Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: We obtain a series of estimates on the number of small integers and small order Farey fractions which belong to a given coset of a subgroup of order $t$ of the group of units of the residue ring modulo a prime $p$, in the case when $t$ is small compared to $p$. We give two applications of these results: to the simultaneous distribution of two high degree monomials $x^{k_1}$ and $x^{k_2}$ modulo $p$ and to a question of J. Holden and P. Moree on fixed points of the discrete logarithm.

Review text

Let \(p\) be a prime number, \(\mathbb F_p\) be the field of the prime order, \(G\) be a multiplicative subgroup of \(\mathbb F_p\setminus\{0\}\), and \(a\in\mathbb F_p\) be an arbitrary element. The authors study the numbers NEWLINE\[NEWLINEU(k,G,a)= \{x: x\in aG,\;|x|\leq k\},\quad V(k,G,a)= \{p: x\in aG,\;\| x\|\leq k\},NEWLINE\]NEWLINE where \(|x|\) and \(\| x\|\) are the least integer and rational heights, correspondingly. The results are effective in the case \(\log\,| G|= o(\log p)\), roughly. There are two applications of the bounds found: to the number of fixed points of the discrete logarithm and to the simultaneous distribution of monomials \(x^{k_1}\), \(x^{k_2}\).

Recommendations

• On the distribution of the residues of small multiplicative subgroups of \(\mathbb F_p\)
• Joint distribution of discrete logarithms
• Product Sets of Rationals, Multiplicative Translates of Subgroups in Residue Rings, and Fixed Points of the Discrete Logarithm
• On distribution of elements of subgroups in arithmetic progressions modulo a prime
• Distribution of residues in approximate subgroups of \(\mathbb F_p^*\)

Cited in

(13)

• Sergei Vladimirovich Konyagin turns 60
• Ratios of small integers in multiplicative subgroups of residue rings
• On balanced subgroups of the multiplicative group
• On small gaps between the elements of multiplicative subgroups of finite fields
• Bounds for multiplicative cosets over fields of prime order
• Correcting noisy exponentiation black-boxes modulo a prime
• The weight distribution of cosets
• On the distribution of elements of semigroups of natural numbers. II
• Joint distribution of discrete logarithms
• Fixed points of the subset sum pseudorandom number generators
• Double and triple character sums and gaps between the elements of subgroups of finite fields
• On the distribution of the residues of small multiplicative subgroups of \(\mathbb F_p\)
• Congruences with intervals and subgroups modulo a prime

This page was built for publication: Distribution of elements of cosets of small subgroups and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2888915)