I'm trying to understand DFT in the context of an integer ring (i.e. the number theoretic transform) and I was wondering how to reduce the number of multiplications by the twiddle factors.
Consider 3-point DFT:
X_0 = x_0 + x_1 + x_2 X_1 = x_0 + x_1 * w + x_2 * w^2 X_2 = x_0 + x_1 * w^2 + x_2 * w^4
Which is the same as:
X_0 = x_0 + x_1 + x_2 X_1 = x_0 + x_1 * w + x_2 * w^2 X_2 = x_0 + x_1 * w^2 + x_2 * w
and it needs 4 (modular) multiplications.
However, apparently it can be also written as:
X_0 = x_0 + x_1 + x_2 X_1 = x_0 + x_1 * w - x_2 - x_2 * w X_2 = x_0 - x_1 - x_1 * w + x_2 * w
which uses only 2 multiplications.
I just cannot figure out how to derive
- x_2 - x_2 * w out of
x_2 * w^2, could someone please fill in the details for me? Are there other ways to reduce the number of multiplications? Is it possible to use just one (or even zero) multiplication? Does similar trick work for larger transforms?