On small gaps between the elements of multiplicative subgroups of finite fields (Q300384)

Let \(p\) be a prime and \(F_p\) the finite field of \(p\) elements. Suppose that \(F_p\) is represented by the set \(\{0, 1,\ldots, p-1\}\). We consider a multiplicative subgroups \(\mathcal G\), \(\mathcal F\) of \(F_p^*\), and an interval of \(H \geq 1\) consecutive integers \(I = \{1,\ldots , H\}\). For \(a,b\in F_p\), we denote by \(R_{a,b}({\mathcal F}, {\mathcal G}; I)\) the number of solutions of the congruence \(a\lambda - b\mu \equiv x\, (\bmod\, p)\), with \(x \in I\) and \(\lambda \in {\mathcal F}\), \(\mu \in {\mathcal G}\). This paper presents several approaches to estimating the quantity \(R_{a,b}({\mathcal F}, {\mathcal G}; I)\) relying on different techniques, and gives upper bounds for it. The results of the paper support the uniqueness assumptions for solutions to additive and multiplicative subgroup rounding problems. which arise during attacks on some careless use of the ElGamal encryption [\textit{D. Boneh} et al., Asiacrypt 2000, Lect. Notes Comput. Sci. 1976, 30--43 (2000; Zbl 0980.94014)].