Wraparound multiplicaton vs mullo

[David Harvey]

On Oct 15, 2009, at 11:19 AM, Niels Möller wrote:

> David Harvey <dmharvey at cims.nyu.edu> writes:
>
>> 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.
>
> This is what I get:
>
> Assume that w is a primitive nth root (n a power of two). Inputs are
> x_k, interpreted as a polynomial
>
>   f(s) = \sum_{k = 0}^{n-1} x_k s^k
>
> Define the transform y_j by
>
>   y_j = f(w^j) = \sum_{k = 0}^{n-1} x_k w^{jk}
>                = \sum_{k = 0}^{n/2-1} (x_k + w^{j n/2} x_{k+n/2}) w^ 
> {jk}
>
> Now consider even elements, j = 2i. since 2i n/2 = 0 (mod n) we get
>
>   y_{2i} = \sum_{k = 0}^{n/2-1} (x_k + w^{2i n/2} x_{k+n/2}) w^{2ik}
>          = \sum_{k = 0}^{n/2-1} (x_k + x_{k+n/2}) (w^2)^ik
>
> And for odd j, j = 2i + 1, we have (2i + 1) n/2 = n/2 (mod n) which  
> implies
>
>   y_{2i+1} = \sum_{k = 0}^{n/2-1} (x_k + w^{n/2} x_{k+n/2}) w^{(2i 
> +1) k}
>            = \sum_{k = 0}^{n/2-1} w^k (x_k + w^{n/2} x_{k+n/2})  
> (w^2)^{ik}
>
> The even and odd parts correspond to the "generalized butterfly"
>
>   y0 = x0 + x1
>   y1 = w^k (x0 + w^{n/2} x1)
>
> in the first stage of the FFT.
>
> And of course, in the usual case, w^{n/2} reduces to -1 and the
> "standard" butterfly operation.

Hmmmm, okay I believe you that this algorithm evaluates at the right  
points.

But I'm still uneasy. What about the following issue: to invert the  
map (x0, x1) -> (y0, y1) above, you need to invert the matrix

1       1
1    w^{n/2}

This has determinant w^{n/2} - 1.

In the case that the modulus is 2^N - 1 and w = 2^{N/n}, we have w^{n/ 
2} - 1 = 2^{N/2} - 1, which is not invertible modulo 2^N - 1. Is this  
a problem?

(If we go back to modulus 2^N + 1 and w = 2^{2N/n}, then w^{n/2} - 1  
= -2, which *is* invertible.)

In fact it feels like you lose some information when you evaluate at  
that set of points.

david