Interpolation of the discrete logarithm in F_q by Boolean functions and by polynomials in several variables modulo a divisor of q - 1

摘要

Recently, Shparlinski proved several results on the interpolation of the discrete logarithm in finite prime fields by Boolean functions. In the first part of the paper, these results are extended to arbitrary finite fields of odd characteristic. More precisely, we prove some complexity lower bounds for Boolean functions representing the lest significant bit of the discrete logarithm in a finite field. In the second part of the paper we obtain lower bounds on the sparsity and the degree of polynomials over F_q in several variables computing the discrete logarithm modulo a prime divisor of q - 1. There results are valid for even characteristic, as well.