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
SN - 0895-4801
VL - 14
SP - 162
EP - 169
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 2
ER -