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

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.
Type de document :
Article dans une revue
Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, Lavoisier, 2010, 29 (1), pp.115-144. 〈10.3166/tsi.29.115-144〉
Liste complète des métadonnées

Littérature citée [45 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00327678
Contributeur : Gilles Villard <>
Soumis le : jeudi 16 octobre 2008 - 09:35:56
Dernière modification le : mardi 16 janvier 2018 - 16:02:04
Document(s) archivé(s) le : mardi 21 septembre 2010 - 17:31:09

Fichier

afrr-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Ivan Morel, Damien Stehlé, Gilles Villard. Analyse numérique et réduction de réseaux. Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, Lavoisier, 2010, 29 (1), pp.115-144. 〈10.3166/tsi.29.115-144〉. 〈ensl-00327678v2〉

Partager

Métriques

Consultations de la notice

363

Téléchargements de fichiers

383