Wraparound multiplicaton vs mullo
David Harvey
dmharvey at cims.nyu.edu
Thu Oct 15 15:29:16 CEST 2009
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
More information about the gmp-devel
mailing list