Skip to Main content Skip to Navigation
Other publications

A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm

Pierrick Gaudry 1 Alexander Kruppa 1 Paul Zimmermann 1
1 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Schönhage-Strassen's algorithm is one of the best known algorithms for multiplying large integers. Implementing it efficiently is of utmost importance, since many other algorithms rely on it as a subroutine. We present here an improved implementation, based on the one distributed within the GMP library. The following ideas and techniques were used or tried: faster arithmetic modulo $2^n+1$, improved cache locality, Mersenne transforms, Chinese Remainder Reconstruction, the $\sqrt{2}$ trick, Harley's and Granlund's tricks, improved tuning. We also discuss some ideas we plan to try in the future.
Complete list of metadatas
Contributor : Pierrick Gaudry <>
Submitted on : Thursday, January 25, 2007 - 9:46:55 AM
Last modification on : Thursday, January 11, 2018 - 6:21:04 AM
Document(s) archivé(s) le : Wednesday, April 7, 2010 - 2:30:40 AM


Files produced by the author(s)


  • HAL Id : inria-00126462, version 1


Pierrick Gaudry, Alexander Kruppa, Paul Zimmermann. A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm. 2007. ⟨inria-00126462v1⟩



Record views


Files downloads