## Abstract

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 Σ^{p-1} _{x,y-1} exp (2πiag^{x}+bg^{y}+cg^{xy}/p) = O(p^{31/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.

Original language | English |
---|---|

Pages (from-to) | 799-812 |

Number of pages | 14 |

Journal | Journal of the London Mathematical Society |

Volume | 59 |

Issue number | 3 |

Publication status | Published - Jun 1999 |