Un problème fondamental en algorithmique est la multiplication rapide de deux entiers de bits. Soit cette complexité, en supposant le modèle des machines de Turing avec un nombre fini de bandes. Jusqu'à récemment, la meilleure borne asymptotique pour était due à Fürer. Plus précisément, il a montré qu'il existe une constante avec

où (pour ) désigne l'itérateur du logarithme, c.à.d.,

Dans un travail récent, nous avons amélioré cette borne. Utilisant un nouveau type d'algorithme, nous avons montré que (et même si une certaine conjecture en théorie des nombres est valide). En optimisant l'approche originale de Fürer, il semble que l'on ne peut pas obtenir mieux que .

Dans un deuxième travail, nous avons également montré comment adapter notre méthode à la multiplication de polynômes de degré à coefficients dans un corps fini . Plus précisément, désignant par cette complexité, nous montrons que

uniformément en . Ici encore, on peut prendre (et même si certaines conjectures en théorie des nombres sont valides). Auparavant, pour fixé, la meilleure borne connue était .

Dans notre exposé, nous survolerons les idées principales derrière ces résultats.

Occasion: JNCF 2014, Luminy, 3 novembre, 2014

Coauthors: David Harvey, Grégoire Lecerf

Documents: slideshow, TeXmacs source