Nussbaumer polynomial multiplication

Josh Liu zliu2 at
Mon May 3 01:50:18 CEST 2004

The Nussbaumer method for cyclic and negacyclic convolution has 
surprisingly good practical timings. It is much better than a symbolic 
Sch\"onhage algorithm, or even the Discrete Weighted Transform version, 
which I implemented alongside the Nussbaumer algorithm. I wonder what 
the implications would be for integer multiplication. I'm working on a 
limb sized operand Nussbaumer algorithm at the moment and I hope that 
it can be competitive with the Sch\"onhage-Strassen method. A simple 
modification should make it viable for the Z/Zp polynomial 
multiplication that Décio Luiz Gazzoni Filho and D. J. Bernstein 
wanted. Also, if someone can give me a good description of the 
Nussbaumer algorithm, better than Knuth's, I would very much appreciate 
it :)

Code is here at and under 

More information about the gmp-discuss mailing list