Incomplete character sums and polynomial interpolation of the discrete logarithm
type: Item
instance of: scholarly article
title: Incomplete character sums and polynomial interpolation of the discrete logarithm
zbMATH Open document ID: 1017.11065
author: Harald Niederreiter
author: Arne Winterhof
published in: Finite Fields and their Applications
publication date: 2002-08-15T00:00:00Z
review text: 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].
Mathematics Subject Classification ID: 11T24
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 1781826
zbMATH Keywords: finite fields
zbMATH Keywords: incomplete character sums
zbMATH Keywords: polynomial interpolation of the discrete logarithm
MaRDI profile type: Publication
full work available at URL: ffta.2001.0334
OpenAlex ID: W2006337912
cites work: On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping.
cites work: A polynomial representation for logarithms in GF(q)
cites work: A short proof for explicit formulas for discrete logarithms in finite fields
cites work: On the distribution of inversive congruential pseudorandom numbers in parts of the period
cites work: Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators
cites work: Equations over finite fields. An elementary approach
cites work: Number theoretic methods in cryptography. Complexity lower bounds
cites work: On the distribution of powers in finite fields
cites work: Q2712132
cites work: Polynomial interpolation of the discrete logarithm
DOI: 10.1006/FFTA.2001.0334
Recommended article: Incomplete character sums over finite fields and their application to the interpolation of the discrete logarithm by Boolean functions
Recommended article: Polynomial interpolation of the discrete logarithm
Recommended article: An estimate of incomplete multiplicative character sum of polynomials
Recommended article: Polynomial Interpolation of the k-th Root of the Discrete Logarithm
Recommended article: Q3497158
Recommended article: Q3505069
Recommended article: Q4314374
Recommended article: Q3539814
Recommended article: Interpolation of the discrete logarithm in finite fields by Boolean functions
Recommended article: Q4277485
description: scientific article; zbMATH DE number 1781826