Wraparound multiplicaton vs mullo

[David Harvey]

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

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

I don't think there is any other procedure that will work. If the  
modulus is N = 2^n - 1 where n is even, then multiplying polynomials  
over Z/N is equivalent to simultaneously multiplying them over Z/N1  
and Z/N2 where N1 = 2^(n/2) - 1 and N2 = 2^(n/2) + 1 (chinese  
remainder theorem). If you use a k-th root of unity, i.e. satisfying  
w^k = 2^n, then the roots of unity will not be distinct modulo N1;  
there will only be k/2 distinct roots of unity modulo N1. So the  
answer modulo N1 cannot possibly be correct, there is true  
information loss.

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

It is not always literally true in the "2^n + 1 ring". For example,

2^(2^5) + 1 = 641 * 6700417

so there are four square roots of 1 in Z/(2^(2^5) + 1). In fact 640 =  
2^7 * 5 and 6700416 = 2^7 * 52347 so there are 2^14 128-th roots of 1!

david