Distribution de la constante d'Hermite et du plus court vecteur dans les réseaux de dimension deux

Henri Laville; Brigitte Vallée

Journal de théorie des nombres de Bordeaux (1994)

  • Volume: 6, Issue: 1, page 135-159
  • ISSN: 1246-7405

Abstract

top
En utilisant la géométrie du demi-plan de Poincaré et des familles de disques classiques - disques de Ford, disques de Farey - nous décrivons les domaines de niveau associés à la constante d'Hermite et au plus court vecteur d'un réseau. Nous en déduisons une évaluation très précise des fonctions de répartition correspondantes, en particulier au voisinage de l'origine.

How to cite

top

Laville, Henri, and Vallée, Brigitte. "Distribution de la constante d'Hermite et du plus court vecteur dans les réseaux de dimension deux." Journal de théorie des nombres de Bordeaux 6.1 (1994): 135-159. <http://eudml.org/doc/247533>.

@article{Laville1994,
abstract = {En utilisant la géométrie du demi-plan de Poincaré et des familles de disques classiques - disques de Ford, disques de Farey - nous décrivons les domaines de niveau associés à la constante d'Hermite et au plus court vecteur d'un réseau. Nous en déduisons une évaluation très précise des fonctions de répartition correspondantes, en particulier au voisinage de l'origine.},
author = {Laville, Henri, Vallée, Brigitte},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {Ford discs; two-dimensional lattice; shortest vector; Hermite constant; Farey discs},
language = {fre},
number = {1},
pages = {135-159},
publisher = {Université Bordeaux I},
title = {Distribution de la constante d'Hermite et du plus court vecteur dans les réseaux de dimension deux},
url = {http://eudml.org/doc/247533},
volume = {6},
year = {1994},
}

TY - JOUR
AU - Laville, Henri
AU - Vallée, Brigitte
TI - Distribution de la constante d'Hermite et du plus court vecteur dans les réseaux de dimension deux
JO - Journal de théorie des nombres de Bordeaux
PY - 1994
PB - Université Bordeaux I
VL - 6
IS - 1
SP - 135
EP - 159
AB - En utilisant la géométrie du demi-plan de Poincaré et des familles de disques classiques - disques de Ford, disques de Farey - nous décrivons les domaines de niveau associés à la constante d'Hermite et au plus court vecteur d'un réseau. Nous en déduisons une évaluation très précise des fonctions de répartition correspondantes, en particulier au voisinage de l'origine.
LA - fre
KW - Ford discs; two-dimensional lattice; shortest vector; Hermite constant; Farey discs
UR - http://eudml.org/doc/247533
ER -

References

top
  1. [CMOS] M.J. Coster, B.A. LaMacchia, A.M. Odlyzko, C.P. Schnorr, An improved low-density subset sum algorithm, Comptes-Rendus du congrès Eurocrypt'91, Lecture Notes in Computer Science547 (1991), 54-67. Zbl0774.11075MR1227795
  2. [Di] G.L. Dirichlet, Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen, J. reine angew. Math.40 (1850), 209-227. 
  3. [DV] H. Daudé, B. Vallée, An upper bound on the average number of iterations of the LLL olgorithm, Theoret. Comput. Sci.123 (1994), 95-115. Zbl0796.11024MR1257206
  4. [FHFLS] A.M. Frieze, J. Hastad, R. Kannan, J.C. Lagarias, A. Shamir, Recowtructing truncated integer variables satisfying linear congruences, SIAM J. Comput.17 (1988), 262-280. Zbl0654.10006MR935340
  5. [Ga] C.F. Gauss, Recherches arithmétiques, traduction française de Disquisitiones Arithmeticae, Blanchard, Paris, 1953. Zbl0051.03003JFM42.0236.19
  6. [HW] G.H. Hardy, E.M. Wright, An introduction to the theory of numbers, Oxford Science Publications, 1989. MR67125
  7. [JS] A. Joux, J. Stern, Improving the critical density of the Lagarias-Odlyzko attack against subset sum problems, Comptes-Rendus du congrès FCT'91, Lecture Notes in Computer Science529 (1991), 258-264. Zbl0925.90301MR1136088
  8. [LLL] A.K. Lenstra, H.W. Lenstra, L. Lovász, Factoring polynomials with rationals coefficients, Math. Ann.261 (1982), 515-534. Zbl0488.12001MR682664
  9. [LO] J C. Lagarias, A.M.Odlyzko, Solving low-density sum problems, J. Assoc. Comput. Mach.32 (1985), 229-246. Zbl0632.94007MR832341
  10. [Si] C.L. Siegel, Lectures on the geometry of numbers, Springer-Verlag, 1989. Zbl0691.10021MR1020761
  11. [St] J. Stern, Secret linear congruential generators are not cryptographically secure, Comptes-Rendus du 28e congrès IEEE-FOCS (1987), 421-426. 
  12. [Va] B. Vallée, An affine algorithm for minima finding in integer lattices of three dimensions, Rapport de Recherche A3L 1989-9, Département de mathématiques, Université de Caen, 1989. 
  13. [VEB] P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in a lattice, Report 81-04, Department of Mathematics, University of Amsterdam, 1981. 
  14. [VF] B. Vallée, P. Flajolet, The lattice reduction algorithm of Gauss: an average case analysis, Comptes-Rendus du 31e congrès IEEE-FOCS (1990), 830-839. MR1150732
  15. [VGT] B. Vallée, M. Girault, P. Toffin, How to guess l-th roots modulo n by reducing lattices bases, Comptes-Rendus du congrès AAECC-88, Rome, juillet 1988, Lecture Notes in Computer Science357 (1989), 427-442. Zbl0692.10005MR1008518

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.