Wraparound multiplicaton vs mullo

[Niels Möller]

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

> 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})

The question is if the denominator is invertible. There should be a
nice closed form using only that w^n = 1 and that n is a power of two.
(When working in a field, we have (x-w)(x-w^2)...(x-w^{n-1}) = (x^n -
1)(x-1) = 1 + x + ... + x^{n-1}, which implies that the denominator
equals n (= 2^k), the factor divided out in the inverse FFT. But the
first step of that argument breaks down in a general ring.

In the more general case of a ring, I'd guess that denominator instead
turns out to be a power of (w^{n/2} - 1) (although I haven't been able
to calculate that).

In the case 2^{2^j} - 1, w = 2^k, this means that interpolation is
impossible. The best we can do is find an f such that f(1) = above
denominator and f(w^k) = 0,k = 1, ..., n - 1.

Maybe it's indeed always impossible, unless w^{n/2} = -1. A possible
argument: In Z_m, any square root r of unity different from ±1 is a
witness proving that m is composite. Furthermore, in this case r^2 - 1
= (r-1)(r+1) is a multiple of n, while both r-1 and r+1 are too small
to be divisible by n. Hence each of (r-1) and (r+1) must contain a non
trivial factor of m, and r-1 is thus not invertible mod m.

It's a different way of saying that the "orthogonality condition" Paul
and you has mentioned really is essential. Yet another different way
to look at it may be to require that w has the property that the n
powers of w give *all* roots of the polynomial x^n - 1 (although it's
not obvious to me if/why that's true the 2^n + 1 ring, when 2^n + 1 is
composite).

In a ring, as opposed to a field, a polynomial of degree n may have
more than n roots. And in Z_{2^n - 1}, the polynomial x^n - 1 has at
least the n+1 roots 1, 2,..., 2^{n-1}, and -1 = 2^n - 2.

Thanks for an enlightning discussion.

/Niels