Nussbaumer polynomial multiplication

[Josh Liu]

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 http://www.student.gsu.edu/~zliu2/centrinia.tar.gz and 
http://www.student.gsu.edu/~zliu2/centrinia.tar.bz2 under 
centrinia/design/base/N/medium/arithmetic/multiplication/Nussbaumer