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 metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00126462
Contributor : Pierrick Gaudry <>
Submitted on : Wednesday, May 23, 2007 - 7:41:16 AM
Last modification on : Thursday, January 11, 2018 - 6:21:04 AM
Long-term archiving on : Tuesday, September 21, 2010 - 1:13:00 PM

File

fft.final.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

766

Files downloads

708