On the discrete logarithm problem

Let F q be a finite field of characteristic p with q = p v elements, g a primitive element, a ≠ 0 an arbitrary element of F q , and x = log g a the discrete logarithm of a to the base g. In this paper we consider the discrete logarithm problem in the case when q ≡ 1(mod 4) and put forward a deterministic algorithm computing the first k ≦ c log n digits x 0 , x 1 , . . . , x k , k < n, in the binary expansion x = x 0 +x 1 2+x 2 2 2 + ··· +x n 2 n of x in a polynomial time.