Wraparound multiplicaton vs mullo
David Harvey
dmharvey at cims.nyu.edu
Thu Oct 15 16:23:55 CEST 2009
On Oct 15, 2009, at 9:48 AM, Niels Möller wrote:
>> 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.
>
> Hmm, I have to think more about this. Is this a different issue than
> w^{n/2} = -1 always being true when w is a primitive nth root in a
> field, but not necessarily true in a general ring, and definitely not
> true for the w = 2 (mod 2^{2^j} - 1).
I think it's basically the same issue.
> I looked at how w^{n/2} != -1 affects the butterfly operations. I
> haven't investigated the inverse FFT. But I would expect that doing
> the forward transform in reverse order, inverting each butterfly
> operation, ought to work fine. No matter if that operation turns out
> to be mathematically equivalent to the forward transform or not.
I haven't thought about this very carefully yet, but my guess is that
the "FFT" algorithm you have in mind, i.e. mimicking the sequence of
butterflies in a genuine FFT, is not really evaluating the input
polynomial at 1, w, ..., w^(2^k - 1). You might want to check this
for k = 2 or something.
My intuition is that the first level of an FFT converts
multiplication modulo x^(2n) - 1 to multiplication mod x^n - 1 and
multiplication mod x^n + 1; the latter is then "twisted" to reduce to
multiplication x^n - 1. But this only works if you have a root of
unity such that w^(n/2) = -1.
david
More information about the gmp-devel
mailing list