Wraparound multiplicaton vs mullo

[David Harvey]

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