Return to search

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

Les réseaux euclidiens sont un outil particulièrement puissant dans<br />plusieurs domaines de l'algorithmique, en cryptographie et en théorie<br />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,<br />et nous développons une nouvelle application dans le domaine<br />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<br />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 <br />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.<br /><br />La plupart des algorithmes décrits dans ce mémoire ont été validés<br />expérimentalement par des implantations, qui sont<br />disponibles à l'url http://www.loria.fr/~stehle.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00011150
Date02 December 2005
CreatorsStehlé, Damien
PublisherUniversité Henri Poincaré - Nancy I
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0019 seconds