Wraparound multiplicaton vs mullo
Paul Zimmermann
Paul.Zimmermann at loria.fr
Thu Oct 15 14:52:32 CEST 2009
Niels,
> > But it might be more tricky for the Schönhage-Strassen FFT (SSFFT)
> > dyadic product. It wants to compute mod x^n+1, not x^n-1 which is
> > redicible over Q.
>
> I'm not sure I understand why it does this.
>
> Lets first look at what the FFT multiplication computes. When I have
> implemented FFT, I let w be a primitive nth root of unity, and I
> evaluate in powers of w, which then are roots of x^n - 1. Wrap-araound
> is then naturally mod B^n - 1.
>
> I'm told (but I haven't looked up the details) that one can also do FFT
> to get wraparound mod B^n + 1. Then the roots of unity used must be
> the roots of x^n + 1, which (in C) differ a factor exp(i pi / n) from
> the roots of x^n - 1. This seems to be what the current mul_fft does.
yes the idea is to premultiply input i by w^(i/2), then you get a factor
of w^(n/2) = -1 for those who wrap around.
> Next, look at the coefficient ring. The only hard requirements are
> that it has a root of unity of the right order, and that the number 2
> is invertible.
>
> In the ring Z_{2^n + 1}, the multiplicative order of 2 is 2 n (since
> 2^n = -1 (mod 2^n + 1), and (-1)^2 = 1). In the ring Z_{2^n - 1}, the
> multiplicative order of 2 is n, since 2^n = 1 (mod 2^n -1).
>
> So if we need a root of unity of order 2^k, and n = 2^j, then
>
> w = 2^{j - k + 1} (j > k + 1)
>
> is suitable when computing mod 2^n + 1, while
>
> w = 2^{j - k} (j > k)
>
> is suitable when computing mod 2^n - 1.
no, you want a primitive root of unity, which requires w^(n/2) = -1,
and this is not the case here.
Paul
More information about the gmp-devel
mailing list