| Titre LLL générique et factorisation des polynômes |
English
version
|
Lieu
INRIA, Projet
CAFÉ
BP 93, 06902 France
Information
Description
L'algorithme de réduction de réseaux LLL joue un rôle fondamental en cryptologie, théorie des nombres et calcul formel (factorisation des polynômes, cf. [2]). Il en existe de nombreuses implémentations sur les entiers longs ou les nombres flottants. Le but de ce stage est de porter l'implémentation de LLL sur GMP de Paul Zimmermann en une implémentation générique (c.a.d. qui fonctionne sur n'importe quels entiers longs) dans le langage Aldor. On utilisera ensuite cette implémentation pour comparer les performances de:
Ces comparaisons devraient permettre d'évaluer la perte éventuelle due à la généricité de l'implémentation ainsi que celle due au passage de GMP au entiers d'Aldor.
Dans une deuxième étape, le programme de factorisation des polynômes univariés de la bibliothèque algebra sera modifié afin d'utiliser LLL dans la phase de recombination, comme décrit dans [1], ce qui devrait améliorer son efficacité de façon importante.
[1] M.van Hoeij, Factoring polynomials and the knapsack problem, Journal of Number Theory, 95, 167-189, (2002)
[2] V.V.Prasolov, Polynomials, Chapter 8, Algorithms and Computations in Mathematics, Vol.11 Springer, Heidelberg.
Outils
Station de travail Unix, langage de programmation Aldor, avec la bibliothèque algebra.
Durée
3-4 mois, niveau maîtrise.