Wraparound multiplicaton vs mullo

[Niels Möller]

Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:

>> while
>> 
>>   w = 2^{j - k}      (j > k)
>> 
>> is suitable when computing mod 2^n - 1.
>
> no, you want a primitive root of unity, which requires w^(n/2) = -1,
> and this is not the case here.

Thanks, that's the second time I forget that requirement!

Actually, I think the above w *is* a primitive nth root of unity, since
it satisfies w^n = 1 and w^i != 1 for 1 <= i < n. But for FFT to
really work, one needs in addition that w^{n/2} = -1.

In a field, this is always the case, since w^{n/2} is clearly a square
root of 1, there are only two such square roots, +1 and -1, and +1 is
excluded since w is a primitive nth root.

But when computing in Z_m where m is not a prime number, there are
more than two square roots of 1 (there are two choices mod each odd
prime factor of m, and these can be combined using CRT, to give (at
least) 2^{number of odd prime factors} square roots. Not sure what
happens if m is a prime power, though).

So Z_m works as a coefficient ring for FFT, with a suitable 2^k'th
root, if either

  m = 2^{2^k} + 1

or

  m = a 2^k + 1,  and prime

Are there any other possibilities?

The previous time I forgot the requirement w^{n/2} = -1, I was
considering using m = b * (a 2^k + 1) where a 2^k + 1 is a prime and a
and b were small. Which also doesn't work.

Just one more thing, before we conclude that mod 2^n + 1 arithmetic is
indeed essential for large-coefficient FFT multiplication:

The reason w^{n/2} = -1 is needed is that we want a simple negation
in the butterfly operations, we want it to look like

  y_0 = x_0 + x_1
  y_1 = w^k (x_0 - x_1)

But if w^{n/2} != -1, we get instead the more general butterfly
operation

  y0 = x0 + x1
  y1 = w^k (x0 + w^{n/2} x1)

and in the case of 2^n-1 arithmetic and w = 2, this is

  y0 = x0 + x1
  y1 = 2^k (x0 + 2^{n/2} x1)

Then multiplication by 2^{n/2} mod 2^n-1 is a rotation (or rather, a
swap of high and low halves) rather than a negation, but it shouldn't
cost more than a negation.

Regards, 
/Niels