TY - JOUR

T1 - On the distribution of Diffie-Hellman triples with sparse exponents

AU - Friedlander, John B.

AU - Shparlinsk, Igor E.

N1 - 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/.

PY - 2001/2

Y1 - 2001/2

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

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

UR - http://www.scopus.com/inward/record.url?scp=0000124225&partnerID=8YFLogxK

U2 - 10.1137/S0895480199361740

DO - 10.1137/S0895480199361740

M3 - Article

AN - SCOPUS:0000124225

VL - 14

SP - 162

EP - 169

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 2

ER -