Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T04:51:34.444Z Has data issue: false hasContentIssue false
  • English
  • Français

ON CERTAIN EXPONENTIAL SUMS AND THE DISTRIBUTION OF DIFFIE–HELLMAN TRIPLES

Published online by Cambridge University Press:  01 June 1999

RAN CANETTI ,
JOHN FRIEDLANDER  and
IGOR SHPARLINSKI
RAN CANETTI
Affiliation:
IBM T. J. Watson Research Center, Yorktown Heights, New York, NY 10598, USA, [email protected]
JOHN FRIEDLANDER
Affiliation:
Department of Mathematics, University of Toronto, Toronto, Ontario M5S 3G3, Canada, [email protected]
IGOR SHPARLINSKI
Affiliation:
School of MPCE, Macquarie University, Sydney, NSW 2109, Australia, [email protected]
Get access

Abstract

Let g be a primitive root modulo a prime p. It is proved that the triples (gx, gy, gxy), 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

formula here

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 (gx, gy, gxy) 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.

Type
Notes and Papers
Information
Journal of the London Mathematical Society , Volume 59 , Issue 3 , June 1999 , pp. 799 - 812
Copyright
The London Mathematical Society 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)