View Single Post
Old 2009-03-02, 14:07   #4
akruppa's Avatar
Aug 2002

9A316 Posts

IIUC, you want to map the product in Z/(2[I]N[/I]+1)Z to Z[x]/(x[I]l[/I]+1) and then not to (Z/(2[I]n[/I]+1)Z)[x]/(xl+1) with n ≥ 2N/l+log2(l), but to (R(Z/(2[I]n[/I]+1)Z))[x]/(x[I]l[/I]-1), where R is some other ring that supports a length-l transform, is large enough that the condition n ≥ 2N/l suffices and the correct product in Z[x]/(x[I]l[/I]+1) can be reconstructed quickly by a CRT from separate convolutions in R[x]/(x[I]l[/I]+1) and (Z/(2[I]n[/I]+1)Z)[x]/(x[I]l[/I]+1). In your FGT suggestion, R = GF(M[I]p[/I]2) for some Mersenne prime M[I]p[/I]. Sounds perfectly feasible.

In fact, in a manuscript of the paper we mentioned an idea Robert Harley told us, but we had to remove it for the final paper due to the page limit. If I understood it correctly, he suggested using e.g. R=Z/232Z and doing some convolution algorithm (grammar-school, Toom-Cook, whatever), but of course there's no reason why we shouldn't use a ring that supports an FFT of the required length. According to Bernstein's "Multidigit Multiplication for Mathematicians" page 11, Karp came up with a similar idea, though I don't quite understand his description so I'm not sure he's talking about the same thing...

So basically, yeah, I think your idea should work.

Btw, if you do a 4-step transform of length ≥212, actual shifts only occur in the "middle step" of applying twiddle factors between the row- and column-transforms, and since the twiddle factor is ωij for matrix entry i,j, you often get an "even enough" exponent that you don't have to do an actual shift again - actual bit-shifts are relatively rare in long Schönhage-Strassen transforms.


Last fiddled with by akruppa on 2009-03-02 at 14:13
akruppa is offline   Reply With Quote