Abstract - kruppa (original) (raw)
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.
Last modified: Mon Jan 19 16:22:35 CET 2009