Wraparound multiplicaton vs mullo

[Paul Zimmermann]

       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