Wraparound multiplicaton vs mullo

[David Harvey]

On Oct 15, 2009, at 8:42 AM, Niels Möller wrote:

> 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)

I think you mean

     w = 2^{2^{j - k + 1}}

and similarly below?

> is suitable when computing mod 2^n + 1, while
>
>   w = 2^{j - k}      (j > k)
>
> is suitable when computing mod 2^n - 1.

Hmmm I'm not sure about this. There is an additional requirement. You  
need the roots of unity to be *principal* roots of unity, i.e. that  
they satisfy some orthogonality relation. This is necessary to ensure  
that the inverse FFT operation really is the inverse of the FFT.

In your above example with the modulus 2^n - 1 (with the correction  
indicated), the problem is that (for example) 1 + w + ... + w^(2^k -  
1) is not zero mod 2^n - 1.

(This property comes for free if you are working over a field, since  
x^n - 1 = 0  ==>  x = 1 or 1 + x + ... + x^(n-1) = 0.)

david