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.
Document type :
Other publications
Complete list of metadata
Contributor : Pierrick Gaudry Connect in order to contact the contributor
Submitted on : Thursday, January 25, 2007 - 9:46:55 AM
Last modification on : Friday, February 26, 2021 - 3:28:08 PM
Long-term archiving on: : 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⟩



Les métriques sont temporairement indisponibles