问数论变换的矩阵计算

EN

我熟悉傅里叶变换和计算DFT和FFT矩阵的快速乘法整数。然而，这是我第一次将NTT应用于\mathbb{Z}_q[x]/x^{n} + 1形式的多项式环。

假设小q=5和n=2，我的元素最多由n-1的所有多项式组成，系数在\mathbb{Z}_{q}中。所有系数的算法都是在\mathbb{Z}_{q}中完成的。

现在，要获得单位的n-th本原根，可以表示Q= N_k + 1 = 2_2 +1，可以让N=2表示N=2的样本大小和k=2，让r=2(是q的原根)。我可以计算w为w = r^k \pmod{q}= 4 \pmod{5} = 4并确认w^{k} \equiv 1 \pmod{q}。4^{2} = 16 \pmod{q} = 1

第一个问题:这种获取w的方法是正确的吗？

我的2×2矩阵会有这样的形式：

\begin{matrix} 1 & 1\\ 1 & w \end{matrix}

现在，考虑w的更高的幂，假设我们用更大的环，并且有一个3乘3的矩阵。设NTT_matrix = \begin{matrix} 1 & 1 & 1 \\ 1 & w & w^2 \\ 1 & w^2 & w^3 \\ \end{matrix}

第二个问题:要计算后向矩阵，让NTT_inv_matrix =

\begin{matrix} 1 & 1 & 1 \\ 1 & w & w^{-2} \\ 1 & w^{-2} & w^{-3} \\ \end{matrix}

乘以N^{-1}。

为了计算w的负幂，我只需取前向矩阵中相应元素的乘积逆，再乘以N^{-1} (样本大小的乘积逆N)。

例如，假设我在前向矩阵中有一个条目：w^3 = 4^3 \pmod{5} = 64 \pmod{5} = 4，向后矩阵中的对应元素将是w^-3。要计算它，是否与(w^{3})^{-1}\pmod{5}相同？在这种情况下，w^3\pmod{5}的乘法逆MI也将是自4*4 \equiv 1 \pmod{5}以来的4。从3*2 \equiv 1 \pmod{5}开始，mod 5的MI(N)为3。那么，计算w^{-3} = MI(w^{3})*MI(N) = 4 * 3 = 12 \pmod{5} = 2呢？

第三个问题:在我填充两个矩阵之后，我可以通过取它们的系数元组来乘以多项式a(x)和b(x)。对于每个多项式，我进行如下操作:如果a(x) =x+3= (a1=1，a0=3)，那么它的元组就是v= (1，3)。我可以通过矩阵向量乘法v*NTT_matrix = v. Same for b(x) say I get v2进行变换.然后是v3 = v`*v2，最后是答案= NTT_inv_matrix(v3)。对，是这样?

第四个问题:这应该给我和a(x)b(x)乘以标准卷积公式一样的答案，对吗？

第五个问题，要定义这样一个环\mathbb{Z}_q[x]/x^{n} + 1，必须要求q是素数，以确保除0以外的所有元素的乘法逆，x^{n} + 1在\pmod{q}中也必须是不可约的，对吗？