On the distribution of Diffie-Hellman triples with sparse exponents

John B. Friedlander*, Igor E. Shparlinsk

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)
2 Downloads (Pure)


Let g be a primitive root modulo a (n + 1)-bit prime p. In this paper we prove the uniformity of distribution of the Diffie-Hellman triples (gcursive Greek chi, gy, gcursive Greek chiy) as the exponents cursive Greek chi and y run through the set of n-bit integers with precisely k nonzero bits in their bit representation provided that k ≥ 0.35n. Such "sparse" exponents are of interest because for these the computation of gcursive Greek chi, gy, gcursive Greek chiy is faster than for arbitrary cursive Greek chi and y. In the latter case, that is, for arbitrary exponents, similar (albeit stronger) uniformity of distribution results have recently been obtained by R. Canetti, M. Larsen, D. Lieman, S. Konyagin [Israel J. Math, 120 (2000), pp. 23-46], and the authors.

Original languageEnglish
Pages (from-to)162-169
Number of pages8
JournalSIAM Journal on Discrete Mathematics
Issue number2
Publication statusPublished - Feb 2001

Bibliographical note

Copyright SIAM Publications. Article archived for private and non-commercial use with the permission of the author and according to publisher conditions. For further information see http://www.siam.org/.


Dive into the research topics of 'On the distribution of Diffie-Hellman triples with sparse exponents'. Together they form a unique fingerprint.

Cite this