On small gaps between the elements of multiplicative subgroups of finite fields (Q300384)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On small gaps between the elements of multiplicative subgroups of finite fields |
scientific article |
Statements
On small gaps between the elements of multiplicative subgroups of finite fields (English)
0 references
27 June 2016
0 references
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)].
0 references
multiplicative subgroups
0 references
finite fields
0 references
additive subgroup rounding problem
0 references
multiplicative subgroup rounding problem
0 references
0 references