Algorithmique de la réduction de réseaux et application à la recherche de pires cas pour l'arrondi de fonctions mathématiques.



Le manuscrit: ps.gz, pdf.
Les transparents de la soutenance: ps.gz, pdf.

Jury

Présidente: Brigitte VALLÉE
Rapporteurs: François MORAIN
Gilles VILLARD
Examinateurs: Peter MARKSTEIN
Gérald TENENBAUM
Paul ZIMMERMANN (Directeur de thèse)

Résumé

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.

Données expérimentales correspondant aux figures du chapitre:
fig4.2, fig4.2bis,
fig4.3,
fig4.4, fig4.4bis,
fig4.5a, fig4.5b, fig4.5c, fig4.5d,
fig4.7a, fig4.7b.

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.

III-2: Amélioration de la méthode de Gal.

Le code correspondant à l'algorithme décrit dans ce chapitre: gatmr-1.0.
Première table pour 2^x.
Table pour sin x.
Seconde table pour 2^x.

III-3: Cryptanalyse du schéma de J.E. Littlewood.

Homepage