Incomplete character sums and polynomial interpolation of the discrete logarithm. (English) Zbl 1017.11065

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}\) [I. E. Shparlinski, Number theoretic methods in cryptography, Birkhäuser, Basel (1999; Zbl 0912.11057), Theorem 4.4].


11T24 Other character sums and Gauss sums
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity
94A60 Cryptography
Full Text: DOI


[1] Coppersmith, D.; Shparlinski, I. E., On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping, J. Cryptology, 13, 339-360 (2000) · Zbl 1038.94007
[2] Mullen, G. L.; White, D., A polynomial representation for logarithms in \(GF (q)\), Acta Arith., 47, 255-261 (1986) · Zbl 0562.12018
[3] Niederreiter, H., A short proof for explicit formulas for discrete logarithms in finite fields, Appl. Algebra Engrg. Comm. Comput., 1, 55-57 (1990) · Zbl 0726.11079
[4] Niederreiter, H.; Shparlinski, I. E., On the distribution of inversive congruential pseudorandom numbers in parts of the period, Math. Comp., 70, 1569-1574 (2001) · Zbl 0983.11048
[5] Niederreiter, H.; Winterhof, A., Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators, Acta Arith., 93, 387-399 (2000) · Zbl 0969.11040
[6] Pólya, G., Über die Verteilung der quadratischen Reste und Nichtreste, Göttinger Nachr., 21-29 (1918) · JFM 46.0265.02
[7] Schmidt, W. M., Equations over Finite Fields: An Elementary Approach (1976), Springer-Verlag: Springer-Verlag Berlin · Zbl 0329.12001
[8] Shparlinski, I. E., Number Theoretic Methods in Cryptography: Complexity Lower Bounds (1999), Birkhäuser: Birkhäuser Basel · Zbl 0912.11057
[9] Vinogradov, I. M., Sur la distribution des résidus et des non-résidus des puissances, Ž. Fiz.-Mat. Obšč. Permsk. Gos. Univ., 1, 94-98 (1918)
[10] Winterhof, A., On the distribution of powers in finite fields, Finite Fields Appl., 4, 43-54 (1998) · Zbl 0910.11055
[11] Winterhof, A., Incomplete additive character sums and applications, (Jungnickel, D.; Niederreiter, H., Finite Fields and Applications (2001), Springer-Verlag: Springer-Verlag Berlin), 462-474 · Zbl 1019.11034
[12] Winterhof, A., Polynomial interpolation of the discrete logarithm, Des. Codes Cryptogr., 25, 63-72 (2002) · Zbl 1008.94015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.