I think I finally found the faster algorithm. It's just plain Schoenhage-Strassen, but with a so called sqrt 2 trick.
Basically, if you want to do a multiplication for polynomials of degree <= 2^l, you need to do a 2^l point FFT, which means you need to work in a ring that has 2^l roots of unity. Working modulo a Fermat number 2^kl+1 alllows you to do this. Now the only thing that stops you doing a 2^(l+1) point transform is the number of roots of unity. In order to get around this, one uses a sqrt(2). Things end up getting multiplied by a power of 2 at some point in the algorithm, but that is clearly easy to shift out by. The timings for MAGMA for a degree 511 polynomial are suspiciously similar to NTL's timings for degree 255. Now, I'm not totally sure about this, since the bit size of the digits has to come in there somewhere, but I'll bet this is what they are doing. Why version 12 of MAGMA seemed to be able to get timings indicating they were able to do a 2^(l+2) point transform I don't know. But the fact they they don't do so now, indicates it wasn't so successful. That is of course unless some underlying bug fix in GMP or some such package hasn't slowed them by a factor of 2 or so. One thing that strikes me is that perhaps with some Kummer theory, one could effectively work in cyclic extensions of Q but using modulo arithmetic, effectively saving even more time, especially if your coefficients are small. Just a random thought anyway. Anyhow, I now have a road map for beating MAGMA at most digit sizes. I am also thinking about a trick which I might be able to use to beat MAGMA's Kronecker-Strassen trick. Bill. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
