14h00 : Fast Integer Multiplication with Schönhage-Strassen's Algorithm. Alexander Kruppa, Projet Cacao, LORIA, Nancy.

This talk describes joint work with Pierrick Gaudry and Paul Zimmermann on an efficient implementation of Schönhage-Strassen's algorithm for integer multiplication in the GMP library. As an introduction we describe the basic principle of performing integer multiplication via polynomial multiplication by multi-point evaluation/interpolation with the FFT, and weighted transforms. Then we present details of the new implementation: fast arithmetic modulo 2^n+1 with GMP's mpn_* primitive functions, improved cache-friendliness of the transform, use of sqrt(2) as a primitive root of unity in the transform, and parameter selection. We also give timings of the new implementation compared to older ones.