Incomplete character sums and polynomial interpolation of the discrete logarithm (Q1609397)

Let \(\mathbb{F}_{q}\) be a finite field with \(q=p^{r}\) elements, \( \{ \omega_{0}, \ldots, \omega_{r-1} \}\) an ordered basis of \(\mathbb{F}_{q}\) over \(\mathbb{F}_{p}\), and \( \zeta_{0}, \zeta_{1}, \ldots , \zeta_{q-1}\) elements of \(\mathbb{F}_{q}\) defined as follows: if \(n=n_{0}+n_{1}p+ \cdots +n_{r-1}p^{r-1}\), \(1 \leq n_{i} < p\), is the \(p\)-adic expansion of \(n\), \(0 \leq n < p\), then \[ \zeta_{n}=n_{0} \omega_{0}+n_{1} \omega_{1}+ \cdots + n_{r-1} \omega_{r-1}. \] For integers \(m,n\), \(M\) and \(N\), with \(0 \leq m,n,M,N < q\), let \(m \oplus n=l \Leftrightarrow \zeta_{m}+ \zeta_{n}= \zeta_{l}\), \(0 \leq l < q\), and \[ S_{M,N}(f,g)=\sum_{n=0}^{N-1} \chi(g( \zeta_{M \oplus n})) \psi( f( \zeta_{M \oplus n})), \] where \( \chi\) and \( \psi\) are multiplicative and additive characters of \(\mathbb{F}_{q}\), respectively, and \(f, g \in \mathbb{F}_{q}[x]\). The authors show that, if \(\text{ord} (\chi)=s\) and \(g(x) \neq \text{ch}(x)^{s}\), \(0 \neq c \in \mathbb{F}_{q}\), then \[ |S_{M,N}(f,g)|< N^{1/2}( \deg(f)+3d-1)^{1/2}+q^{1/2}, \] where \(d\) is the number of distinct roots of \(g\) in its splitting field over \(\mathbb{F}_{q}\). This improves a previous result of the second author [Finite Fields Appl. 4, 43-54 (1998; Zbl 0910.11055)]. Then they use the above bound for \(S_{M,N}(f,g)\) to show that if \(f(x)\) is a polynomial over \(\mathbb{F}_{q}\) which coincides with the discrete logarithm of \(\mathbb{F}_{q}\) at the points \( \zeta_{M \oplus n}\), for \(0 \leq n \leq N-1\), \(M \oplus n \neq 0\), then \[ \deg (f) > \frac{1}{3} \left(1- \frac{2 \pi r}{p} \right)^{2} \frac{N} {q^{1/2}}-2, \] for \(p > 2 \pi r\). This extends the corresponding result for the case of prime finite fields \(\mathbb{F}_{p}\) [\textit{I. E. Shparlinski}, Number theoretic methods in cryptography, Birkhäuser, Basel (1999; Zbl 0912.11057), Theorem 4.4].