Séminaire du 26 janvier 2009. 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.
Virginie Collette
Last modified: Mon Jan 19 16:22:35 CET 2009