Double character sums over elliptic curves and finite fields (Q1001764): Difference between revisions

Let \(p\) be a prime number, \(\mathbb{F}_{p}\) a finite field with \(p\) elements, \( \mathbb{F}_{p}^{*}= \mathbb{F}_{p} \setminus \{0 \}\), and \(E\) an elliptic curve over \( \mathbb{F}_{p}\), defined by an affine Weierstrass equation of the form \[ y^{2}=x^{3}+ax+b, \qquad b,c \in \mathbb{F}_{p}, \quad 4a^{3}+27b ^{2} \neq 0. \] Let \(E( \mathbb{F}_{p})\) be the set of \( \mathbb{F}_{p}\)-rational points of \(E\), together with the point at infinity \(O\), which forms a finite abelian group with the zero element \(O\), and let \(G=(\mathbf x(G), \mathbf y(G)) \in E( \mathbb{F}_{p})\), \( G \neq O\) be a point of order \(T \geq 1\). The authors consider the double sums \[ W_{c}(U, V)= \sum_{u \in U} \sum_{v \in V} \alpha_{u} \beta_{v} e^{2 \pi i c \mathbf x(uvG)/p}, \quad \alpha_{u}, \beta_{v} \in \mathbb{C}, \quad c \in \mathbb{F}_{p}^{*}, \] where \(U\) and \(V\) are arbitrary subsets of the ring of integers modulo \(T\), and prove that \[ W_{c}(U,V) \ll AB T^{5/6} ( \#U \#V)^{1/2}p^{1/12+ \varepsilon}, \] where \[ A= \max_{u \in U} | \alpha_{u}|, \qquad B= \max_{v \in V} | \beta_{ v}|, \] and the implied constant depends only on \( \varepsilon\). Then using the above result they estimate the sums \[ S_{c}(N)= \sum_{n \leq N} \Lambda(n) e^{2 \pi i c \mathbf{x}(nG)/p}, \qquad c \in \mathbb{F}_{p}^{*}, \] where \( \Lambda(n)\) is the von Mangoldt function. Moreover, the authors consider the purely periodic sequences of points \(U_{n} \in E( \mathbb{F}_{p})\) generated by the rule \[ U_{n}=eU_{n-1}, \qquad n=1,2, \ldots, \qquad U_{0}=G, \] where \(e \geq 2\) is an integer with \(\gcd(e,T)=1\) of multiplicative order \(t\) modulo \(T\), and prove that \[ \sum_{n=0}^{N-1} e^{ 2 \pi i c \mathbf{x}(U_{n})} \ll T^{5/9} N^{1/3} p^{1/18+ \varepsilon}. \] The concluding section concerns the double multiplicative character sums \[ W_{c}(U,V; \chi)= \sum_{u \in U} \sum_{v \in V} \alpha_{u} \beta_{v} \chi( \vartheta^{uv}+c), \quad \alpha_{u}, \beta_{v} \in \mathbb{C}, \quad c \in \mathbb{F}_{p}^{*}, \] where \( \vartheta \in \mathbb{F}_{p}^{*}\) is an element of multiplicative order \(T\) and \(U, V \subset \mathbb{Z}_{T}\). It is shown that \[ W_{c}(U,V; \chi) \ll AB T^{3/4}( \#U \#V)^{1/2}p^{1/8+ \varepsilon}, \qquad \chi \neq \chi_{0}, \] where again \[ A= \max_{u \in U}| \alpha_{u}|. \qquad B= \max_{v \in V}| \beta_{v}|, \] and the implied constant depends only on \( \varepsilon\). As a consequence of the last result the authors obtain the estimate \[ \sum_{n \leq N} \Lambda(n) \chi( \vartheta^{n}+c) \ll (NT^{-1}p^{1/2}+N^{2/3}T^{1/2}p^{1/12})N^{ \varepsilon}, \qquad c \in \mathbb{F}_{p}^{*}. \] In addition, the authors estimate multiplicative character sums of the form \[ \sum_{n=0}^{N-1} \chi( \vartheta^{e^{n}+c}), \qquad \chi \neq \chi_{0}, \qquad c \in \mathbb{F}_{p}^{*}, \] where \(e \geq 2\) is an integer with \(\gcd(e,T)=1\) of multiplicative order \(t\) modulo \(T\) and \(1 \leq N \leq t\). They also briefly explain the cryptographic significance of the estimates stated in the paper. In particular, they note that the above upper bound for the double sums \(W_{c}(U,V)\) implies various uniformity distribution results for the Diffie-Hellman triples \[ (\mathbf x(uG), \mathbf x(vG), \mathbf x(uvG)) \] on elliptic curves.