New bounds on exponential sums related to the Diffie–Hellman distributions

Jean Bourgain

doi:10.1016/j.crma.2004.03.027

Logic

New bounds on exponential sums related to the Diffie–Hellman distributions

Presented by: Jean Bourgain

Jean Bourgain ¹

¹ Institute for Advanced Study, School of Mathematics, Princeton, NJ 08540, USA

Comptes Rendus. Mathématique, Volume 338 (2004) no. 11, pp. 825-830.

Abstract
Résumé

Given $θ \in 𝔽_{p}^{*}$ (p prime) of multiplicative order t>p^δ, we obtain nontrivial bounds on exponential sums

\sum_{s' = 1}^{t} |\sum_{s = 1}^{t} e_{p} (a θ^{s} + c θ^{ss'})|

as well as the corresponding incomplete sums. These estimates are of relevance to several issues, such as the Diffie–Hellman distributions in cryptography, prime divisors of ‘sparse integers’, the distribution

\mod p

of Mersenne numbers M_q=2^q−1 (q prime). The method is closely related to that of Bourgain and Konyagin (C. R. Acad. Sci. Paris, Ser. I 337 (2) (2003) 75–80).

Soit $θ \in 𝔽_{p}^{*}$ (p premier) d'ordre multiplicatif t>p^δ, on obtient des bornes non-triviales sur les sommes exponentielles

\sum_{s' = 1}^{t} |\sum_{s = 1}^{t} e_{p} (a θ^{s} + c θ^{ss'})|

de même que les sommes incomplètes correspondantes. Ces estimations sont importantes dans divers contextes, comme, par exemple, les distributions de Diffie–Hellman en cryptography, les diviseurs premiers d'entiers à représentation « clairsemée », la distribution

\mod p

de nombres de Mersenne (M_q=2^q−1 (q premier)). Cette méthode est très proche de celle de Bourgain et Konyagin (C. R. Acad. Sci. Paris, Ser. I 337 (2) (2003) 75–80).

Received: 2004-02-24
Accepted: 2004-03-02
Published online: 2004-04-17

DOI: 10.1016/j.crma.2004.03.027

Author's affiliations:

Jean Bourgain ¹

¹ Institute for Advanced Study, School of Mathematics, Princeton, NJ 08540, USA

@article{CRMATH_2004__338_11_825_0,
     author = {Jean Bourgain},
     title = {New bounds on exponential sums related to the {Diffie{\textendash}Hellman} distributions},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {825--830},
     publisher = {Elsevier},
     volume = {338},
     number = {11},
     year = {2004},
     doi = {10.1016/j.crma.2004.03.027},
     language = {en},
}

TY  - JOUR
AU  - Jean Bourgain
TI  - New bounds on exponential sums related to the Diffie–Hellman distributions
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 825
EP  - 830
VL  - 338
IS  - 11
PB  - Elsevier
DO  - 10.1016/j.crma.2004.03.027
LA  - en
ID  - CRMATH_2004__338_11_825_0
ER  -

%0 Journal Article
%A Jean Bourgain
%T New bounds on exponential sums related to the Diffie–Hellman distributions
%J Comptes Rendus. Mathématique
%D 2004
%P 825-830
%V 338
%N 11
%I Elsevier
%R 10.1016/j.crma.2004.03.027
%G en
%F CRMATH_2004__338_11_825_0

Jean Bourgain. New bounds on exponential sums related to the Diffie–Hellman distributions. Comptes Rendus. Mathématique, Volume 338 (2004) no. 11, pp. 825-830. doi : 10.1016/j.crma.2004.03.027. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2004.03.027/

References
Cited by

[1] W.D. Banks; A. Conflitti; J.B. Friedlander; I.E. Shparlinski Exponential sums over Mersenne numbers, Compositio Math., Volume 140 (2004) no. 1, pp. 15-30

[2] J. Bourgain On the Erdös–Volkmann and Katz–Tao ring conjectures, Geom. Funct. Anal., Volume 13 (2003) no. 2, pp. 334-365

[3] J. Bourgain, N. Katz, T. Tao, A sum-product theorem in finite fields and applications, Geom. Funct. Anal., in press

[4] J. Bourgain; S.V. Konyagin Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order, C. R. Math. Acad. Sci. Paris, Ser. I, Volume 337 (2003) no. 2, pp. 75-80

[5] R. Canetti; J. Friedlander; S. Konyagin; M. Larsen; D. Lieman; I. Shparlinski On the statistical properties of Diffie–Hellman distributions, Israel J. Math. A, Volume 120 (2000), pp. 23-46

[6] J.B. Friedlander; S. Konyagin; I.E. Shparlinski Some doubly exponential sums over $ℤ_{m}$ , Acta Arith., Volume 105 (2002) no. 4, pp. 349-370

[7] S. Konyagin, Private communications

[8] I. Shparlinski Prime divisors of sparse integers, Period. Math. Hungar., Volume 96 (2003) no. N2, pp. 215-222

Cited by Sources:

Comments - Policy