On the distribution of the Diffie-Hellman pairs

Igor E. Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


Let Fp be a prime field of p elements and let g be an element of Fp 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 × Fp, where x runs through • the residue ring ℤt modulo t (that is, as in the classical Diffie-Hellman scheme); • The all k-sums x = ai1 + ⋯ + aik, 1 ≤ i1 < ⋯ <ik ≤ n, where a1, ⋯, an ∈ ℤt 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.

Original languageEnglish
Pages (from-to)131-141
Number of pages11
JournalFinite Fields and their Applications
Issue number2
Publication statusPublished - 2002


Dive into the research topics of 'On the distribution of the Diffie-Hellman pairs'. Together they form a unique fingerprint.

Cite this