On the Distribution of the Diffie–Hellman Pairs

Let p be a prime field of p elements and let g be an element of p of multiplicative order t modulo p. We show that for any >0 and t≥p1/3+ the distribution of the Diffie–Hellman pairs (x, gx) is close to uniform in the Cartesian product t× p, where x runs through• the residue ring modulo (that is, as in the classical Diffie–Hellman scheme);• The all -SUMS =+•••+, 1≤<•••<≤, where ,…, are selected at random (that is, an in the recently introduced Diffie–Hellman scheme with precomputation). These results are new and nontrivial even if t=p−1, that is, if g is a primitive root. The method is based on some bounds of exponential sums.