Nussbaumer polynomial multiplication

[Décio Luiz Gazzoni Filho]

-----BEGIN PGP SIGNED MESSAGE-----
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 http://careybloodworth.tripod.com/nussbaumer.htm. Lastly D. 
J. Bernstein himself wrote something here: http://cr.yp.to/papers/m3.pdf 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.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAlZs1FXvAfvngkOIRAln+AJ93Mqhj/EoAn2BceHv7srmr18X2gwCfX9GO
lm6XFg1fRCYqmy1KCLasclI=
=oQNx
-----END PGP SIGNATURE-----