Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials

Nina Brandstaetter and Arne Winterhof

Address.
Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Strasse 69, A-4040 Linz, Austria

E-mail. nina.brandstaetter@oeaw.ac.at

E-mail. arne.winterhof@oeaw.ac.at

Abstract.
We obtain lower bounds on degree and additive complexity of real polynomials approximating the discrete logarithm in finite fields of even characteristic. These bounds complement earlier results for finite fields of odd characteristic.

AMSclassification. 11T24, 11T71, 94A60.

Keywords. Discrete logarithm, polynomial approximation, character sums.