Incomplete Character Sums and Polynomial Interpolation of the Discrete Logarithm
✍ Scribed by Harald Niederreiter; Arne Winterhof
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 99 KB
- Volume
- 8
- Category
- Article
- ISSN
- 1071-5797
No coin nor oath required. For personal study only.
✦ Synopsis
In the "rst part of the paper, certain incomplete character sums over a "nite "eld F N P are considered which in the case of "nite prime "elds F N are of the form
, where A and N are integers with 14N(p, g and f are polynomials over F N , and denotes a multiplicative and an additive character of F N . Excluding trivial cases, it is shown that the above sums are at most of the order of magnitude NpP. Recently, Shparlinski showed that a polynomial f over the integers which coincides with the discrete logarithm of the "nite prime "eld F N for N consecutive elements of F N must have a degree at least of the order of magnitude Np. In this paper this result is extended to arbitrary F N P . The proof is based on the above new bound for incomplete hybrid character sums.
2002 Elsevier Science (USA)