I've been working on code to multiply polynomials using NTT (FFT), and I made 2 different implementations, and used existing ones to validate, for example: https://www.nayuki.io/page/number-theoretic-transform-integer-dft, https://github.com/iblue/ntt.
The problem is that all results seem to be shifted once to the left (multiplied by x) like this:
0 0 1 1 (x + 1)
*
0 0 1 1 (x + 1)
=
1 2 1 0 (1x^3 + 2x^2 + x) // Should be 0 1 2 1
Also, the trivial case 1*1 is wrong the same way:
0 0 0 1 (1)
*
0 0 0 1 (1)
=
0 0 1 0 (x) // Should be 0 0 0 1 (1)
I have no clue why this is happening, and it is not mentioned in any of the articles I've read so far.
What am I missing?