Analyse numérique et réduction de réseaux

摘要

The algorithmic facet of euclidean lattices is a frequent tool in computer science and mathematics. It mainly relies on the LLL reduction, making worthwile efficiency improvements. Schnorr proved that the LLL algorithm can be speeded up if one computes approximations to the underlying Gram-Schmidt orthogonalisations. Without approximations, these computations dominate the cost of the reduction. Recently, classical tools from the field of numerical analysis have been revisited and improved in order to strengthen Schnorr's approach, and further reducing the costs. We describe these developments, and show especially how floating-point computations may be introduced at various levels in the reduction process.%L'algorithmique des réseaux euclidiens est un outil fréquemment utilisé en informatique et en mathématiques. Elle repose essentiellement sur la réduction LLL qu 'il est donc important de rendre aussi efficace que possible. Une approche initiée par Schnorr consiste à effectuer des calculs approchés pour estimer les orthogonalisations de Gratn-Schmidt sous-jacentes. Sans approximations, ces calculs dominent le co?t de la réduction. Récemment, des outils classiques d'analyse numérique ont été revisités et améliorés, pour exploiter plus systématiquement l'idée de Schnorr et réduire les co?ts. Nous décrivons ces développements, notamment comment l'algorithmique en nombres flottants peut être introduite à plusieurs niveaux dans la réduction.