Polynomial representations of the Diffie-Hellman mapping

We obtain lower bounds on the degrees of polynomials representing the Diffie-Hellman mapping (g^x,g^y) → g^xy, where g is a primitive root of a finite field double-struck F sign_q of q elements. These bounds are exponential in terms of log q. In particular, these results can be used to obtain lower bounds on the parallel arithmetic complexity of breaking the Diffie-Hellman cryptosystem. The method is based on bounds of numbers of solutions of some polynomial equations.