NTT multiplication.

Aleksey Bader bader at
Tue May 12 22:04:26 CEST 2009

Hi GMP developers!

I have a couple of questions about FFT-based multiplication algorithms in

As follows from one of the projects is
devoted to implementation of FFT-based algorithm combined with Chinese
Reminder Theorem. It's claimed that there are 2 implementations of this
algorithm (by Tommy Färnqvist and Niels Möller).

Q1. Are there available source code for those implementations?

The reason I'm asking is because I did the same job when I was working on my
master thesis 2 years ago. It'd be very curious to compare or maybe improve
our implementations.
Actually, I was able to find Tommy's master thesis and his code seemed to be
up to twice as fast as the code in GMP 4.1.4.

Q2. What about 4.3.*? Is it still could be profitable in comparison with the
current GMP multiplication? (sorry for such dump question, but I'm not
followed gmp changes)

Thanks in advance,

P.S. Reletevly recent, Martin Furer
multiplication algorithm with very low asymptotic complexity.
Q3. Any known (tries of) implementions (in GMP O:)? Maybe someone think
about it (disregard to author's claim that his method outperforms
Schönhage-Strassen on "astonomically large numbers" :-) )?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the gmp-devel mailing list