Les réseaux euclidiens sont un outil particulièrement puissant dans
plusieurs domaines de l'algorithmique, en cryptographie et en théorie
algorithmique des nombres par exemple. L'objet du présent mémoire est dual:
nous améliorons les algorithmes de réduction des réseaux,
et nous développons une nouvelle application dans le domaine
de l'arithmétique des ordinateurs. En ce qui concerne l'aspect algorithmique,
nous nous intéressons aux cas des petites dimensions (en dimension un, où il
s'agit du calcul de pgcd, et aussi en dimensions 2 à 4), ainsi qu'à la
description d'une nouvelle variante de l'algorithme LLL, en dimension
quelconque. Du point de vue de l'application, nous utilisons la méthode
de Coppersmith permettant de trouver les petites racines de polynômes
modulaires multivariés, pour calculer les pires cas pour l'arrondi des
fonctions mathématiques, quand la fonction, le mode d'arrondi, et la précision
sont donnés. Nous adaptons aussi notre technique aux mauvais cas simultanés
pour deux fonctions. Ces deux méthodes sont des pré-calculs
coûteux, qui une fois effectués permettent d'accélérer les implantations
des fonctions mathématiques élémentaires en précision fixée, par exemple
en double précision.
La plupart des algorithmes décrits dans ce mémoire ont été validés
expérimentalement par des implantations, qui sont
disponibles à l'url http://www.loria.fr/~stehle.
Partie I: Préliminaires.
I-1. Éléments de géométrie des nombres.
I-2. Éléments d'arithmétique flottante.
Partie II: Algorithmique de la réduction des réseaux.
II-1: L'algorithme rapide de pgcd binaire.
Ici se trouvent
des résultats expérimentaux sur la division binaire généralisée.
Ces résultats ont été validés par l'analyse en moyenne de
Daireaux, Maume-Deschamp et
Vallée.
II-2: La réduction de réseaux en petite dimension.
III-3: L'algorithme LLL en arithmétique flottante.
Ici se trouve un réseau de dimension 55
qui fait boucler le LLL_FP de NTL, avec delta=0.99.
Ce réseau fait aussi boucler le LLL de Magma, une fois que certaines options
ont été désactivées:
M:= LLL(L: InitialSort := false, Delta := 0.99, UseGram:= false, UnderflowCheck:=false , Large := false);
Ici se trouve un réseau de dimension 35
pour lequel le LLL_FP de NTL (avec delta=0.99) se rend compte que les
calculs flottants deviennent faux et recommence en précision plus élevée.
III-4: Résultats expérimentaux autour de l'algorithme LLL.
La bibliothèque fplll-1.2.
Quelques bibliothèques contenant une implantation de l'algorithme LLL: NTL,
Magma,
Pari GP,
LiDIA.
Ici se trouve un réseau de dimension 83
qui fait boucler la variante prouvée de fplll-1.2 quand on force la
précision à 113 bits (quadruple précision), avec delta=0.99. Ici se trouve un réseau de dimension 3
qui fait boucler le G_LLL_FP de NTL, avec delta=0.99.
Partie III: Pires cas pour l'arrondi de fonctions.
III-1: Recherche des pires cas de fonctions mathématiques.
Le code correspondant à l'algorithme décrit dans ce chapitre:
wclr-1.1.
