Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\). (Q1811103): Difference between revisions

\textit{I. E. Shparlinski} [Number theoretic methods in cryptography, Prog. Comput. Sci. Appl. Logic 17. Birkhäuser, Basel (1999; Zbl 0912.11057)] established several complexity lower bounds on the discrete logarithm in finite prime fields. These results are extended to arbitrary finite fields of odd characteristic. In detail, complexity lower bounds for Boolean functions representing the least significant bit of the discrete logarithm are shown. Furthermore, lower bounds on the sparsity and the degree of polynomials over \(GF(q)\) in several variables computing the discrete logarithm modulo a prime divisor of \(q-1\) are given. The latter results are valid for characteristic 2 as well. Most of the proofs are based on bounds for character sums.