fft - 数论变换乘法移位

Question

我一直在研究使用 NTT (FFT) 将多项式相乘的代码，我做了 2 种不同的实现，并使用现有的实现来验证，例如：https ://www.nayuki.io/page/number-theoretic-transform -integer-dft，https://github.com/iblue/ntt。

问题是所有结果似乎都向左移动一次（乘以 x），如下所示：

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

此外，平凡的案例 1*1 也是错误的：

0 0 0 1 (1)
*
0 0 0 1 (1)
=
0 0 1 0 (x) // Should be 0 0 0 1 (1)

我不知道为什么会发生这种情况，到目前为止我读过的任何文章都没有提到它。

我错过了什么？