Premium
On Certain Exponential Sums and the Distribution of Diffie–Hellman Triples
Author(s) -
Canetti Ran,
Friedlander John,
Shparlinski Igor
Publication year - 1999
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s002461079900736x
Subject(s) - mathematics , modulo , combinatorics , constant (computer programming) , exponential function , prime (order theory) , primitive root modulo n , upper and lower bounds , fraction (chemistry) , discrete mathematics , cryptography , distribution (mathematics) , algorithm , mathematical analysis , chemistry , organic chemistry , computer science , programming language
Let g be a primitive root modulo a prime p . It is proved that the triples ( g x , g y , g xy ), x , y = 1, …, p −1, are uniformly distributed modulo p in the sense of H. Weyl. This result is based on the following upper bound for double exponential sums. Let ε>0 be fixed. Then∑ x , y = 1 p ‐ 1exp ( 2 π i a g x + b g x + c g x p ) = O ( p31 / 16 + ε)uniformly for any integers a , b , c with gcd( a , b , c , p ) = 1. Incomplete sums are estimated as well. The question is motivated by the assumption, often made in cryptography, that the triples ( g x , g y , g xy ) cannot be distinguished from totally random triples in feasible computation time. The results imply that this is in any case true for a constant fraction of the most significant bits, and for a constant fraction of the least significant bits.