no. 11
Logic
New bounds on exponential sums related to the Diffie–Hellman distributions
[Nouvelles estimées des sommes exponentielles liées aux distributions de Diffie–Hellman]

Présenté par : Jean Bourgain

Bourgain, Jean1
1 Institute for Advanced Study, School of Mathematics, Princeton, NJ 08540, USA
Comptes Rendus. Mathématique, Tome 338 (2004) no. 11, pp. 825-830.

Soit θ∈𝔽 p * (p premier) d'ordre multiplicatif t>pδ, on obtient des bornes non-triviales sur les sommes exponentielles

∑ s'=1 t ∑ 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 (Mq=2q−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).

Given θ∈𝔽 p * (p prime) of multiplicative order t>pδ, we obtain nontrivial bounds on exponential sums

∑ s'=1 t ∑ 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 Mq=2q−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).

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2004.03.027
Bourgain, Jean 1

1 Institute for Advanced Study, School of Mathematics, Princeton, NJ 08540, USA 
@article{CRMATH_2004__338_11_825_0,
     author = {Bourgain, Jean},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2004.03.027/}
}
TY  - JOUR
AU  - Bourgain, Jean
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2004.03.027/
DO  - 10.1016/j.crma.2004.03.027
LA  - en
ID  - CRMATH_2004__338_11_825_0
ER  - 
%0 Journal Article
%A Bourgain, Jean
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2004.03.027/
%R 10.1016/j.crma.2004.03.027
%G en
%F CRMATH_2004__338_11_825_0
Bourgain, Jean. New bounds on exponential sums related to the Diffie–Hellman distributions. Comptes Rendus. Mathématique, Tome 338 (2004) no. 11, pp. 825-830. doi : 10.1016/j.crma.2004.03.027. http://www.numdam.org/articles/10.1016/j.crma.2004.03.027/

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

[2] Bourgain, J. 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] Bourgain, J.; Konyagin, S.V. 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] Canetti, R.; Friedlander, J.; Konyagin, S.; Larsen, M.; Lieman, D.; Shparlinski, I. On the statistical properties of Diffie–Hellman distributions, Israel J. Math. A, Volume 120 (2000), pp. 23-46

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

[7] S. Konyagin, Private communications

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

Cité par Sources :