Multiplication d'entiers en temps quasi-linéaire

Mots clés: FFT, multiplication, entiers, multi-précision.

Le but de ce projet est de comparer différents algorithmes de multiplication d’entiers asymptotiquement rapides. On s’intéressera principalement à la famille d’algorithmes de Toom-Cook, et à l’algorithme en $O(n\log n\log\log n)$ de Schönage-Strassen.

Résumé

Objectifs

• Implanter les algorithmes de multiplication de Toom-Cook.

• Implanter l’algorithme de Schönage-Strassen.

• Comparer les implantation par des benchmarks, déterminer les points de seuil.

Références

• R. Crandall, C. Pomerance. Prime numbers: a computational perspective.

• P. Gaudry, A. Kruppa, P. Zimmermann. A GMP-based Implementation of Schönhage-Strassen’s Large Integer Multiplication Algorithm.