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 F-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.