Nussbaumer polynomial multiplication

Décio Luiz Gazzoni Filho decio at
Mon May 3 03:06:26 CEST 2004

Hash: SHA1

On Sunday 02 May 2004 20:50, Josh Liu wrote:
> 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 :)

There's a fairly clear description on R. Crandall & C. Pomerance's book, Prime 
numbers: a computational perspective. There's even an explicit algorithm for 
it. (Note: although the book is mostly about computational number theory, the 
last chapter is on fast arithmetic algorithms. It's a pretty good 
introduction to the subject and I don't think you'll regret buying this one, 
even if you don't care about CNT.) Crandall mentions that a book of his, 
Topics in Advanced Scientific Computation, describes in detail the 
implementation of Nussbaumer convolution and enhacements to it.

Outside of this, you could have a look at Carey Bloodworth's page, which has a 
lot of material on fast multiplication, and a bit on Nussbaumer convolution 
in particular at Lastly D. 
J. Bernstein himself wrote something here: but 
I found it quite difficult to follow, so I'm not sure it's going to help you.

You may consider joining the pi-hacks Yahoogroup too, lots of fast 
multiplication freaks lurk there, including Carey Bloodworth.

Version: GnuPG v1.2.4 (GNU/Linux)


More information about the gmp-discuss mailing list