Wraparound multiplicaton vs mullo&In-Reply-To=<nn3a5jrd4j.fsf at stalhein.lysator.liu.se>

[Tommy Färnqvist]

On Oct 16, 2009, at 3:50 AM, Niels Möller wrote:

>> 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?
>
>This looks like a serious problem. Then the question is: Is the
>interpolation problem not solvable, or is it solvable by some other
>(potentially much more expensive) procedure?
>
>If interpolation is possible, then there must exist a polynomial f(s)
>such that f(1) = 1 and f(w^k) = 0 for all k = 1, ..., n-1. That
>polynomial, if it exists, is
>
>          (s-w)(s-w^2) ... (s-w^{n-1})
>  f(s) = ------------------------------
>          (1-w)(1-w^2) ... (1-w^{n-1})


Perhaps I am stating the obvious, but I think some of the answers to these questions can be found here:
http://en.wikipedia.org/wiki/Vandermonde_matrix

Best regards,
Tommy