Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Pierrick Gaudry Connect in order to contact the contributor
Submitted on : Wednesday, May 23, 2007 - 7:41:16 AM
Last modification on : Friday, February 26, 2021 - 3:28:08 PM
Long-term archiving on: : Tuesday, September 21, 2010 - 1:13:00 PM

Files produced by the author(s)




Pierrick Gaudry, Alexander Kruppa, Paul Zimmermann. A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm. ISSAC 2007, Jul 2007, Waterloo, Ontario, Canada. pp.167-174, ⟨10.1145/1277548.1277572⟩. ⟨inria-00126462v2⟩



Record views


Files downloads