自己做网站教程友情链接交换平台免费

深入理解NTT

• 中国剩余定理 (CRT)：环 $R$ 上的有限个理想 { I i } \{I_i\} {Ii​}，存在同态映射
  $$\sigma :R/\bigcap _i{I}_i\to \prod _{i}R/I_i$$

  如果它们两两互素 $I_i+I_j=R$，那么 $\sigma$ 是环同构

• 在多项式环上，如果$f,g\in R[x]$且$gcd(f,g)=1$，那么存在环同构
  $$\begin{array}{rl}\varphi :R[x]/(f(x)g(x))& \cong R[x]/(f(x))\times R[x]/(g(x))\\ \varphi (h)& =(h\mathrm{mod}f,h\mathrm{mod}g)\end{array}$$

• 环$Z_q[x]/(x^n-1)$，其中$n=2^k,n\mid q-1$，取${\xi }_n\in Z_q$

• 容易验证如下分解等式：
  $$\begin{array}{rl}{x}^n-1& =(x^{\frac{n}{2}}-{\xi }_n^0)(x^{\frac{n}{2}}-{\xi }_n^{\frac{n}{2}})\\ x^{\frac{n}{2}}-{\xi }_n^0& =(x^{\frac{n}{4}}-{\xi }_n^0)(x^{\frac{n}{4}}-{\xi }_n^{\frac{2n}{4}})\\ x^{\frac{n}{2}}-{\xi }_n^{\frac{n}{2}}& =(x^{\frac{n}{4}}-{\xi }_n^{\frac{n}{4}})(x^{\frac{n}{4}}-{\xi }_n^{\frac{3n}{4}})\\ \cdots & \end{array}$$
  分解过程，如图：

  $j=0$	$j=1$	$j=2$
  		$x^{\frac{n}{4}}-{\xi }_n^0$，${\xi }_n^0=({\xi }_n^{\frac{n}{4}}{)}^{br{v}_2(0)}$
  	$x^{\frac{n}{2}}-{\xi }_n^0$，${\xi }_n^0=({\xi }_n^{\frac{n}{2}}{)}^{br{v}_1(0)}$
  		$x^{\frac{n}{4}}-{\xi }_n^{\frac{2n}{4}}$，${\xi }_n^{\frac{2n}{4}}=({\xi }_n^{\frac{n}{4}}{)}^{br{v}_2(1)}$
  $x^n-1=x^n-{\xi }_n^0$
  		$x^{\frac{n}{4}}-{\xi }_n^{\frac{n}{4}}$，${\xi }_n^{\frac{n}{4}}=({\xi }_n^{\frac{n}{4}}{)}^{br{v}_2(2)}$
  	$x^{\frac{n}{2}}-{\xi }_n^{\frac{n}{2}}$，${\xi }_n^{\frac{n}{2}}=({\xi }_n^{\frac{n}{2}}{)}^{br{v}_1(1)}$
  		$x^{\frac{n}{4}}-{\xi }_n^{\frac{3n}{4}}$，${\xi }_n^{\frac{3n}{4}}=({\xi }_n^{\frac{n}{4}}{)}^{br{v}_2(3)}$

• 令$f(x)\in Z_q[x]/(x^n-1)$，简记$f_{b_1\cdots b_j}(x):=f(x)\mathrm{mod}{x}^{\frac{n}{2^j}}-({\xi }_n^{\frac{n}{2^j}}{)}^{br{v}_j(b_1\cdots b_j)}$，其中$b_1\cdots b_j$是分解路径。

  对应的位置关系，如图：

  $j=0$	$j=1$	$j=2$
  		$f_{00}=f(x)\mathrm{mod}{x}^{\frac{n}{4}}-{\xi }_n^0$
  	$f_0=f(x)\mathrm{mod}{x}^{\frac{n}{2}}-{\xi }_n^0$
  		$f_{01}=f(x)\mathrm{mod}{x}^{\frac{n}{4}}-{\xi }_n^{\frac{2n}{4}}$
  $f=f(x)\mathrm{mod}{x}^n-1$
  		$f_{10}=f(x)\mathrm{mod}{x}^{\frac{n}{4}}-{\xi }_n^{\frac{n}{4}}$
  	$f_1=f(x)\mathrm{mod}{x}^{\frac{n}{2}}-{\xi }_n^{\frac{n}{2}}$
  		$f_{11}=f(x)\mathrm{mod}{x}^{\frac{n}{4}}-{\xi }_n^{\frac{3n}{4}}$

• 令阵列$f[i]$是多项式$f(x)$的系数向量，即
  $$f(x)=\sum _{i=0}^{n-1}f[i]x^i\mathrm{mod}{x}^n-1$$
  模掉$x^{\frac{n}{2}}-a$，为
  $$f(x)=\sum _{i=0}^{\frac{n}{2}-1}(f[i]+af[i+\frac{n}{2}])x^i\mathrm{mod}{x}^{\frac{n}{2}}-a$$

• 令阵列$f_0[i]$是多项式$f_0(x)$的系数向量，阵列$f_1[i]$是多项式$f_1(x)$的系数向量，那么
  $$\begin{array}{r}{f}_0(x)=\sum _{i=0}^{\frac{n}{2}-1}(f[i]+{\xi }_n^{0}f[i+\frac{n}{2}])x^i\mathrm{mod}{x}^{\frac{n}{2}}-{\xi }_n^0\\ f_1(x)=\sum _{i=0}^{\frac{n}{2}-1}(f[i]+{\xi }_n^{\frac{n}{2}}f[i+\frac{n}{2}])x^i\mathrm{mod}{x}^{\frac{n}{2}}-{\xi }_n^{\frac{n}{2}}\end{array}$$
  其中${\xi }_n^{\frac{n}{2}}=-{\xi }_n^0$；后续的分解类似。

• 使用CT蝴蝶：
  $$\begin{array}{ccccccccc}{f}_{b_1\cdots b_{j-1}}[i]& \to & \to & \to & \to & \to & \oplus & \to & f_{b_1\cdots b_{j-1}|0}[i]\\ & & & \searrow & & \nearrow & & & \\ & & & & \cdot & & & & \\ & & & \nearrow & & \searrow & & & \\ f_{b_1\cdots b_{j-1}}[i+\frac{n}{2}]& \to & \otimes & \to & \to & \to & \ominus & \to & f_{b_1\cdots b_{j-1}|1}[i]\\ & & \uparrow & & & & & & \\ & & ({\xi }_n^{\frac{n}{2^j}}{)}^{brv(b_1\cdots b_{j-1}|0)}& & & & & & \end{array}$$

• 阵列的迭代流程，如下图所示：

  $j=0$	$j=1$	$j=2$
  $f[0]$	$f_0[0]$	$f_{00}[0]$
  $⋮$	$⋮$	$⋮$
  $⋮$	$f_0[\frac{n}{4}-1]$	$f_{00}[\frac{n}{4}-1]$
  $⋮$	$f_0[\frac{n}{4}]$	$f_{01}[0]$
  $⋮$	$⋮$	$⋮$
  $f[\frac{n}{2}-1]$	$f_0[\frac{n}{2}-1]$	$f_{01}[\frac{n}{4}-1]$
  $f[\frac{n}{2}]$	$f_1[0]$	$f_{10}[0]$
  $⋮$	$⋮$	$⋮$
  $⋮$	$f_1[\frac{n}{4}-1]$	$f_{10}[\frac{n}{4}-1]$
  $⋮$	$f_1[\frac{n}{4}]$	$f_{11}[0]$
  $⋮$	$⋮$	$⋮$
  $f[n-1]$	$f_1[\frac{n}{4}-1]$	$f_{11}[\frac{n}{4}-1]$

  即，使用CT蝴蝶，将阵列$f[i]$迭代运算$j$次，将会得到$2^j$个多项式，它们是$f(x)\mathrm{mod}{x}^{2^{k-j}}-{\xi }_{ji}$，这里的${\xi }_{ji}=({\xi }_n^{\frac{n}{2^j}}{)}^{br{v}_j(b_1\cdots b_j)}$代表第$j$列、第$i=dec(b_1\cdots b_j)$行的模多项式的常数项。

  如果迭代$k$次，将会得到$2^k$个多项式，它们就是$f({\xi }_n^{brv(i)})=f(x)\mathrm{mod}x-{\xi }_n^{brv(i)}$，$f(x)$的$2^k$个key-value pair

• 根据以上分析，我们使用CT蝴蝶迭代，没必要迭代到最后一层。将$f$分解为若干$f\mathrm{mod}{x}^h-{\xi }_{ji}$即可，这便是不完全NTT了。

• 由于
  $$\begin{array}{r}{f}_{b_1\cdots b_{j-1}|0}[i]=f_{b_1\cdots b_{j-1}}[i]+({\xi }_n^{\frac{n}{2^j}}{)}^{brv(b_1\cdots b_{j-1}|0)}{f}_{b_1\cdots b_{j-1}}[i+\frac{n}{2}]\\ f_{b_1\cdots b_{j-1}|1}[i]=f_{b_1\cdots b_{j-1}}[i]-({\xi }_n^{\frac{n}{2^j}}{)}^{brv(b_1\cdots b_{j-1}|0)}{f}_{b_1\cdots b_{j-1}}[i+\frac{n}{2}]\end{array}$$
  那么
  $$\begin{array}{rl}{f}_{b_1\cdots b_{j-1}}[i]& =\frac{f_{b_1\cdots b_{j-1}|0}[i]+f_{b_1\cdots b_{j-1}|1}[i+\frac{n}{2}]}{2}\\ f_{b_1\cdots b_{j-1}}[i+\frac{n}{2}]& =\frac{f_{b_1\cdots b_{j-1}|0}[i]-f_{b_1\cdots b_{j-1}|1}[i+\frac{n}{2}]}{2\cdot ({\xi }_n^{\frac{n}{2^j}}{)}^{brv(b_1\cdots b_{j-1}|0)}}\end{array}$$

• 使用GS蝴蝶来进行INTT：
  $$\begin{array}{ccccccccc}2\cdot f_{b_1\cdots b_{j-1}}[i]& \leftarrow & \leftarrow & \leftarrow & \oplus & \leftarrow & \leftarrow & \leftarrow & f_{b_1\cdots b_{j-1}|0}[i]\\ & & & & & \nwarrow & & \swarrow & \\ & & & & & & \cdot & & \\ & & & & & \swarrow & & \nwarrow & \\ 2\cdot f_{b_1\cdots b_{j-1}}[i+\frac{n}{2}]& \leftarrow & \otimes & \leftarrow & \ominus & \leftarrow & \leftarrow & \leftarrow & f_{b_1\cdots b_{j-1}|1}[i]\\ & & \uparrow & & & & & & \\ & & \frac{1}{({\xi }_n^{\frac{n}{2^j}}{)}^{brv(b_1\cdots b_{j-1}|0)}}& & & & & & \end{array}$$

  从第$j$层使用GS蝴蝶做INTT，迭代$j$次后，将得到阵列$f^{\prime }[i]=2^{j}f[i]\mathrm{mod}q$

  容易恢复多项式：$f(x)⟺f^{\prime }[i]\cdot (2^j{)}^{-1}\mathrm{mod}q$

总结

• FFT迭代的每一步，都是利用CRT，$Z_q[x]/(x^n-\xi )\cong Z_q[x]/(x^{n/2}-{\xi }^{\prime })\times Z_q[x]/(x^{n/2}-{\xi }^{\prime \prime })$

• 将 $f\mathrm{mod}{x}^n-\xi$ 分解为 $f\mathrm{mod}{x}^{n/2}-{\xi }^{\prime },f\mathrm{mod}{x}^{n/2}-{\xi }^{\prime \prime }$，其中$x^n-\xi =(x^{n/2}-{\xi }^{\prime })(x^{n/2}-{\xi }^{\prime \prime })$

• 迭代$j$次后，所得结果是：$2^j$个多项式$f_{bi{n}_j(i)}=f\mathrm{mod}{x}^{n/2^j}-{\xi }_{ji},i=0,1,\cdots ,2^j-1$

• 用CT蝴蝶实现FFT，用GS蝴蝶实现IFFT

• 假设$f^{(1)},f^{(2)}$在第$j$层的分解是$f_{bi{n}_j(i)}^{(1)},f_{bi{n}_j(i)}^{(2)}$，那么：$f^{(1)}\cdot f^{(2)}⟺f_{bi{n}_j(i)}^{(1)}\cdot f_{bi{n}_j(i)}^{(2)}$，左右都是卷积。

• 如果$j=k$，那么：$f^{(1)}\cdot f^{(2)}⟺f^{(1)}({\xi }^i)\cdot f^{(2)}(({\xi }^i))$，右边退化为阵列乘积。