A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm - Archive ouverte HAL Access content directly
Conference Papers Year : 2007

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

(1) , (1) , (1)
1
Pierrick Gaudry
Alexander Kruppa
• Function : Author
• PersonId : 757608
• IdRef : 149703511
Paul Zimmermann

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.

Dates and versions

inria-00126462 , version 1 (25-01-2007)
inria-00126462 , version 2 (23-05-2007)

Identifiers

• HAL Id : inria-00126462 , version 2
• DOI :

Cite

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⟩

729 View