Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Strasse 69, A-4040 Linz, Austria
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.