10h30 : Multiplication de polynômes binaires. Emmanuel Thomé, Projet Cacao, LORIA, Nancy.

Le problème de la multiplication de polynômes à coefficients dans GF(2), de par son aspect élémentaire, apparaît dans de nombreux contextes. Nous étudions différents algorithmes pour réaliser cette opération, en poursuivant l'objectif de couvrir une large gamme de degrés possibles. Nous étudions ainsi les aspects « bas niveau » liés au microprocesseur pour la multiplication en petit degré, puis différentes variantes des algorithmes de Karatsuba et Toom-Cook, et enfin deux algorithmes différents de type FFT. Nous proposons différentes améliorations qui se traduisent par une accélération des algorithmes. Nous comparons les résultats obtenus à ceux de la bibliothèque NTL.