Analyse numérique et réduction de réseaux
Ivan Morel, Damien Stehlé et Gilles Villard
Résumé : 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 Gram-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.
Download: pdf.
Homepage