On Certain Exponential Sums and the Distribution of Diffie–Hellman Triples

Let g be a primitive root modulo a prime p . It is proved that the triples ( g x , g y , g xy ), x , y = 1, …, p −1, are uniformly distributed modulo p in the sense of H. Weyl. This result is based on the following upper bound for double exponential sums. Let ε>0 be fixed. Then∑ x , y = 1 p ‐ 1exp ( 2 π i a g x + b g x + c g x p ) = O ( p31 / 16 + ε)uniformly for any integers a , b , c with gcd( a , b , c , p ) = 1. Incomplete sums are estimated as well. The question is motivated by the assumption, often made in cryptography, that the triples ( g x , g y , g xy ) cannot be distinguished from totally random triples in feasible computation time. The results imply that this is in any case true for a constant fraction of the most significant bits, and for a constant fraction of the least significant bits.