Incomplete character sums and polynomial interpolation of the discrete logarithm

Abstract

In the first part of the paper, certain incomplete character sums over a finite field Fp r are considered which in the case of finite prime fields Fp are of the form ∑n=A A+N-1 x(g(n)ψ(f(n)), where A and N are integers with 1 ≤ N < p, g and f are polynomials over Fp, and χ denotes a multiplicative and ψ an additive character of Fp. Excluding trivial cases, it is shown that the above sums are at most of the order of magnitude N1/2pr/4. Recently, Shparlinski showed that a polynomial f over the integers which coincides with the discrete logarithm of the finite prime field Fp for N consecutive elements of Fp must have a degree at least of the order of magnitude Np-1/2. In this paper this result is extended to arbitrary Fp r. The proof is based on the above new bound for incomplete hybrid character sums. © 2002 Elsevier Science (USA).