Wraparound multiplicaton vs mullo
Niels Möller
nisse at lysator.liu.se
Thu Oct 15 15:36:19 CEST 2009
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
More information about the gmp-devel
mailing list