Wraparound multiplicaton vs mullo

[Niels Möller]

David Harvey <dmharvey at cims.nyu.edu> writes:

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

You're right. It's difficult to get the number of exponentiations
right...

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

Regards,
/Niels