CRT

令 R R R是基环 (base ring)，那么 R [ x ] R[x] R[x]是一元多项式环。

如果 f , g ∈ R [ x ] f,g \in R[x] f,g∈R[x]且 g c d ( f , g ) = 1 gcd(f,g)=1 gcd(f,g)=1，那么存在环同构：
ϕ : R [ x ] / ( f ( x ) g ( x ) ) ≅ R [ x ] / ( f ( x ) ) × R [ x ] / ( g ( x ) ) ϕ ( h ) = ( h m o d    f ,   h m o d    g ) \begin{aligned} \phi:R[x]/(f(x)g(x)) &\cong R[x]/(f(x)) \times R[x]/(g(x))\\ \phi(h) &= (h \mod{f},\, h \mod{g}) \end{aligned} ϕ:R[x]/(f(x)g(x))ϕ(h)​≅R[x]/(f(x))×R[x]/(g(x))=(hmodf,hmodg)​
且：
i f ϕ ( h ) = ( h f ,   h g ) l e t g f − 1 ⋅ g ≡ 1 m o d    f f g − 1 ⋅ f ≡ 1 m o d    g t h e n h ≡ h f ⋅ g ⋅ g f − 1 + h g ⋅ f ⋅ f g − 1 m o d    f g \begin{aligned} if &\\ & \phi(h) = (h_f,\, h_g)\\ let &\\ & g_f^{-1} \cdot g \equiv 1 \mod{f}\\ & f_g^{-1} \cdot f \equiv 1 \mod{g}\\ then &\\ & h \equiv h_f \cdot g \cdot g_f^{-1} + h_g \cdot f \cdot f_g^{-1} \mod{fg}\\ \end{aligned} ifletthen​ϕ(h)=(hf​,hg​)gf−1​⋅g≡1modffg−1​⋅f≡1modgh≡hf​⋅g⋅gf−1​+hg​⋅f⋅fg−1​modfg​

(cyclic) NTT 【模 x 2 k − 1 x^{2^k}-1 x2k−1】

• FFT是DFT的快速算法，对于 n n n长向量，计算复杂度为 O ( n log ⁡ n ) O(n\log{n}) O(nlogn)

• NTT是工作在素域上 R = F p R=F_p R=Fp​的FFT，因此它不含复数运算，计算结果没有舍入误差。

• 令 n = 2 k n=2^k n=2k，NTT需要寻找 x n − 1 x^n-1 xn−1的本原单位根： ξ ∈ F p \xi \in F_p ξ∈Fp​

• ∃ ξ ∈ F p    ⟺    n ∣ p − 1 \exist \xi \in F_p \iff n|p-1 ∃ξ∈Fp​⟺n∣p−1，形如 p = 2 k p ′ + 1 p=2^kp'+1 p=2kp′+1的素数，叫做NTT友好的素数 (NTT-friendly prime)

• 给定本原元 g ∈ F p g \in F_p g∈Fp​，那么n次本原单位根为： ξ n = g p − 1 n \xi_n = g^{\frac{p-1}{n}} ξn​=gnp−1​

• 易知： g c d ( x − ξ i , x − ξ j ) = 1 ,   i ≢ j gcd(x-\xi^i,x-\xi^j)=1,\,i \not \equiv j gcd(x−ξi,x−ξj)=1,i​≡j，利用CRT：
  ϕ : R [ x ] / ( x n − 1 ) → R [ x ] / ( x − 1 ) × R [ x ] / ( x − ξ ) × ⋯ × R [ x ] / ( x − ξ n − 1 ) \begin{aligned} \phi:R[x]/(x^n-1) \rightarrow R[x]/(x-1) \times R[x]/(x-\xi) \times \cdots \times R[x]/(x-\xi^{n-1})\\ \end{aligned} ϕ:R[x]/(xn−1)→R[x]/(x−1)×R[x]/(x−ξ)×⋯×R[x]/(x−ξn−1)​

• 如果 f ( x ) = ∑ i = 0 n f i x i f(x)=\sum_{i=0}^nf_ix^i f(x)=∑i=0n​fi​xi，那么 f ( x ) ≡ f ( a ) m o d    x − a f(x) \equiv f(a) \mod{x-a} f(x)≡f(a)modx−a；因此，上式为： ϕ ( f ) = [ f ( 1 ) , f ( ξ ) , ⋯   , f ( ξ n − 1 ) ] \phi(f)=[f(1),f(\xi),\cdots,f(\xi^{n-1})] ϕ(f)=[f(1),f(ξ),⋯,f(ξn−1)]

• 当我们只关注多项式乘积时，分解的顺序不重要。由于 n = 2 k n=2^k n=2k，可利用CT蝴蝶或者GS蝴蝶实现NTT，注意比特反序。

• 由于DFT和IDFT公式相似，所以也可以用NTT计算IDFT：将 ξ \xi ξ替换为 ξ − 1 \xi^{-1} ξ−1，并将结果再乘以 1 n \frac{1}{n} n1​

• 将环元素 f ( x ) ∈ R [ x ] / ( x n − 1 ) f(x) \in R[x]/(x^n-1) f(x)∈R[x]/(xn−1)写作 n n n长的系数向量： [ f n − 1 , ⋯   , f 1 , f 0 ] [f_{n-1},\cdots,f_1,f_0] [fn−1​,⋯,f1​,f0​]

• 环元素乘法 h ( x ) = f ( x ) g ( x ) m o d    x n − 1 h(x) = f(x)g(x) \mod{x^n-1} h(x)=f(x)g(x)modxn−1    ⟺    \iff ⟺ 系数向量循环卷积 h k = f ( k ) ⊛ g ( k ) : = ∑ t = 0 n − 1 f ( k − t ) g t h_k = f(k) \circledast g(k) := \sum_{t=0}^{n-1}f_{(k-t)}g_{t} hk​=f(k)⊛g(k):=∑t=0n−1​f(k−t)​gt​，这里 ( k − t ) : = k − t m o d    n (k-t) := k-t \mod{n} (k−t):=k−tmodn

• 对于 f , g ∈ R [ x ] / ( x n − 1 ) f,g \in R[x]/(x^n-1) f,g∈R[x]/(xn−1)，做NTT分别得到 [ f ( ξ ) , ⋯   , f ( ξ n − 1 ) , f ( ξ n ) ] [f(\xi),\cdots,f(\xi^{n-1}),f(\xi^n)] [f(ξ),⋯,f(ξn−1),f(ξn)]和 [ g ( ξ ) , ⋯   , g ( ξ n − 1 ) , g ( ξ n ) ] [g(\xi),\cdots,g(\xi^{n-1}),g(\xi^n)] [g(ξ),⋯,g(ξn−1),g(ξn)]

• f ( x ) g ( x )    ⟺    [ f ( ξ j ) g ( ξ j ) ] f(x)g(x) \iff [f(\xi^j)g(\xi^j)] f(x)g(x)⟺[f(ξj)g(ξj)]，左边是多项式乘积(向量卷积)，右边是阵列乘积。

NTT变体

Negacyclic NTT【模 x 2 k − 1 + 1 x^{2^{k-1}}+1 x2k−1+1】

• 对于 R [ x ] / ( x n + 1 ) R[x]/(x^n+1) R[x]/(xn+1)，其上多项式乘法是反循环卷积 (Negacyclic convolution)。

• 第一种解法

  • 如果 n = 2 k − 1 n=2^{k-1} n=2k−1，寻找 2 n 2n 2n次本原单位根： ξ 2 n ∈ R \xi_{2n} \in R ξ2n​∈R；由于 ( x 2 n − 1 ) = ( x n + 1 ) ( x n − 1 ) (x^{2n}-1)=(x^n+1)(x^n-1) (x2n−1)=(xn+1)(xn−1)，且 g c d ( x n + 1 , x n − 1 ) = 1 gcd(x^n+1,x^n-1)=1 gcd(xn+1,xn−1)=1，因此 R [ x ] / ( x 2 n − 1 ) ≅ R [ x ] / ( x n + 1 ) × R [ x ] / ( x n − 1 ) R[x]/(x^{2n}-1) \cong R[x]/(x^n+1) \times R[x]/(x^n-1) R[x]/(x2n−1)≅R[x]/(xn+1)×R[x]/(xn−1)

  • x 2 n − 1 x^{2n}-1 x2n−1的所有根是 { ξ 2 n , ξ 2 n 2 , ⋯   , ξ 2 n 2 n } \{\xi_{2n},\xi_{2n}^2,\cdots,\xi_{2n}^{2n}\} {ξ2n​,ξ2n2​,⋯,ξ2n2n​}，而 x n − 1 x^{n}-1 xn−1的所有根是 { ξ 2 n 2 , ξ 2 n 4 , ⋯   , ξ 2 n 2 n } \{\xi_{2n}^2,\xi_{2n}^4,\cdots,\xi_{2n}^{2n}\} {ξ2n2​,ξ2n4​,⋯,ξ2n2n​}，因此 x n + 1 x^{n}+1 xn+1的所有根是 { ξ 2 n 1 , ξ 2 n 3 , ⋯   , ξ 2 n 2 n − 1 } \{\xi_{2n}^1,\xi_{2n}^3,\cdots,\xi_{2n}^{2n-1}\} {ξ2n1​,ξ2n3​,⋯,ξ2n2n−1​}

  • R [ x ] / ( x n + 1 ) ≅ R [ x ] / ( x − ξ ) × ⋯ × R [ x ] / ( x − ξ 2 n − 1 ) R[x]/(x^n+1) \cong R[x]/(x-\xi) \times \cdots \times R[x]/(x-\xi^{2n-1}) R[x]/(xn+1)≅R[x]/(x−ξ)×⋯×R[x]/(x−ξ2n−1)

  • 模 x n + 1 x^n+1 xn+1的Negacyclic NTT，可以看做模 x 2 n − 1 x^{2n}-1 x2n−1的(cyclic) NTT的一半：先对长度 n n n的 { f i } \{f_i\} {fi​}补零到 2 n 2n 2n长序列，计算NTT，截取结果 { f ( ξ 1 ) , f ( ξ 3 ) , ⋯   , f ( ξ 2 n − 1 ) } \{f(\xi^1),f(\xi^3),\cdots,f(\xi^{2n-1})\} {f(ξ1),f(ξ3),⋯,f(ξ2n−1)}

  • 对于IDFT，直接用上述 Negacyclic NTT 实现即可。

• 第二种解法 (感觉更好理解)

  • 令 Y = ξ 2 n X Y=\xi_{2n} X Y=ξ2n​X，则 R [ X ] / ( X n + 1 ) ≅ R [ Y ] / ( Y n − 1 ) R[X]/(X^n+1) \cong R[Y]/(Y^n-1) R[X]/(Xn+1)≅R[Y]/(Yn−1)
    ϕ ( ∑ i = 0 n − 1 f i x i ) : = ∑ i = 0 n − 1 f i ξ − i ( ξ x ) i = ∑ i = 0 n − 1 ( f i ξ − i ) y i ϕ − 1 ( ∑ i = 0 n − 1 g i y i ) : = ∑ i = 0 n − 1 g i ξ i ( ξ − 1 y ) i = ∑ i = 0 n − 1 ( g i ξ i ) x i \begin{aligned} \phi(\sum_{i=0}^{n-1}f_ix^i) :=& \sum_{i=0}^{n-1}f_i \xi^{-i} (\xi x)^i = \sum_{i=0}^{n-1}(f_i \xi^{-i}) y^i\\ \phi^{-1}(\sum_{i=0}^{n-1}g_iy^i) :=& \sum_{i=0}^{n-1}g_i \xi^{i} (\xi^{-1} y)^i = \sum_{i=0}^{n-1}(g_i \xi^{i}) x^i\\ \end{aligned} ϕ(i=0∑n−1​fi​xi):=ϕ−1(i=0∑n−1​gi​yi):=​i=0∑n−1​fi​ξ−i(ξx)i=i=0∑n−1​(fi​ξ−i)yii=0∑n−1​gi​ξi(ξ−1y)i=i=0∑n−1​(gi​ξi)xi​

  • 先把 f ( x ) ∈ R [ X ] / ( X n + 1 ) f(x) \in R[X]/(X^n+1) f(x)∈R[X]/(Xn+1)映射到 g = ϕ ( f ) ∈ R [ Y ] / ( Y n − 1 ) g = \phi(f) \in R[Y]/(Y^n-1) g=ϕ(f)∈R[Y]/(Yn−1)，然后做(cyclic) NTT得到 { g ( 1 ) , g ( ξ ) , ⋯   , g ( ξ n − 1 ) } \{g(1),g(\xi),\cdots,g(\xi^{n-1})\} {g(1),g(ξ),⋯,g(ξn−1)}

  • 对于IDFT，先用NTT从 { g ( ξ j ) } \{g(\xi^j)\} {g(ξj)}得到 g ∈ R [ Y ] / ( Y n − 1 ) g \in R[Y]/(Y^n-1) g∈R[Y]/(Yn−1)，然后输出 f = ϕ − 1 ( g ) f=\phi^{-1}(g) f=ϕ−1(g)

Incomplete NTTs【不分解到最底层】

• 对于 f ∈ R [ x ] / ( x n − 1 ) ,   n = 2 k f \in R[x]/(x^n-1),\,n=2^k f∈R[x]/(xn−1),n=2k，使用FFT对它做 l l l层分解，得到 2 l 2^l 2l个 R [ x ] / ( x n / 2 l − ξ i ) R[x]/(x^{n/2^l}-\xi_i) R[x]/(xn/2l−ξi​)的直积： [ f m o d    x n / 2 l − ξ i , ⋯   ] [f \mod{x^{n/2^l}-\xi_i},\cdots] [fmodxn/2l−ξi​,⋯]
• 对于 f , g ∈ R [ x ] / ( x n − 1 ) f,g \in R[x]/(x^n-1) f,g∈R[x]/(xn−1)，做不完全NTT，分别得到 [ f 1 , ⋯   , f 2 l ] [f_1,\cdots,f_{2^l}] [f1​,⋯,f2l​]和 [ g 1 , ⋯   , g 2 l ] [g_1,\cdots,g_{2^l}] [g1​,⋯,g2l​]
• 大卷积 f ( x ) g ( x ) f(x)g(x) f(x)g(x)    ⟺    \iff ⟺ 若干小卷积 [ f j ( x ) g j ( x ) ] [f_j(x)g_j(x)] [fj​(x)gj​(x)]，左右两边都是多项式乘积 (如果分解到第 k k k层，多项式乘法退化为阵列乘法)
• 对于固定参数 p , n p,n p,n的商环 F p [ x ] / ( x n − 1 ) F_p[x]/(x^n-1) Fp​[x]/(xn−1)，根据硬件实现的差异 (寄存器、运算器的数目，支持运算数的比特长度)，选择合适的分解层数，对于小卷积直接使用经典算法即可。

Good’s Trick【模 x h ⋅ 2 k − 1 x^{h \cdot 2^k}-1 xh⋅2k−1】

• 对于 R [ x ] / ( x n − 1 ) R[x]/(x^n-1) R[x]/(xn−1)，假如 n = h ⋅ 2 k n=h \cdot 2^k n=h⋅2k，其中 h h h是奇数。我们令 x = y w x=yw x=yw，且 y 2 k − 1 = − 1 ,   w h − 1 + w h − 2 + ⋯ + w = − 1 y^{2^{k-1}}=-1,\,w^{h-1}+w^{h-2}+\cdots+w=-1 y2k−1=−1,wh−1+wh−2+⋯+w=−1

• 做映射：
  ϕ : R [ x ] / ( x h ⋅ 2 k ) → R [ y , w ] x i ↦ y i m o d    2 k w i m o d    h \begin{aligned} \phi: & R[x]/(x^{h \cdot 2^k}) \rightarrow R[y,w]\\ & x^i \mapsto y^{i \mod{2^k}} w^{i \mod{h}} \end{aligned} ϕ:​R[x]/(xh⋅2k)→R[y,w]xi↦yimod2kwimodh​
  令 b ( y , w ) = ϕ ( a ( x ) ) b(y,w)=\phi(a(x)) b(y,w)=ϕ(a(x))，则： deg ⁡ y b < 2 k ,   deg ⁡ w b < h \deg_y b < 2^k,\,\deg_w b < h degy​b<2k,degw​b<h

• 记 b ( y , w ) = ∑ i = 0 h − 1 w i b i ( y ) b(y,w)=\sum_{i=0}^{h-1}w^ib_i(y) b(y,w)=∑i=0h−1​wibi​(y)，其中 b i ( y ) ∈ R [ y ] / ( y 2 k − 1 ) b_i(y) \in R[y]/(y^{2^k}-1) bi​(y)∈R[y]/(y2k−1)

• Good’s Permutation：用一维阵列 a [ i ] a[i] a[i]记录 a ( x ) = ∑ i = 0 h ⋅ 2 k − 1 a i x i a(x) = \sum_{i=0}^{h \cdot 2^k -1}a_ix^i a(x)=∑i=0h⋅2k−1​ai​xi；用二维阵列 b [ i ] [ j ] b[i][j] b[i][j]记录 b ( y , w ) = ∑ i = 0 h − 1 ∑ j = 0 2 k − 1 b i j w i y j b(y,w) = \sum_{i=0}^{h-1}\sum_{j=0}^{2^k-1}b_{ij}w^iy^j b(y,w)=∑i=0h−1​∑j=02k−1​bij​wiyj，其中的每一行 b [ i ] b[i] b[i]记录了 b i ( y ) b_i(y) bi​(y)

• a ∈ R [ x ] / ( x h ⋅ 2 k − 1 ) a \in R[x]/(x^{h \cdot 2^k}-1) a∈R[x]/(xh⋅2k−1)，我们映射到 b = ϕ ( a ) = ∑ i = 0 h − 1 w i b i ( y ) b=\phi(a)=\sum_{i=0}^{h-1}w^ib_i(y) b=ϕ(a)=∑i=0h−1​wibi​(y)；然后对每一行 b [ i ] b[i] b[i]，并行地做 h h h次大小 2 k 2^k 2k的NTT，得到NTT域结果：阵列 B [ i ] [ j ] B[i][j] B[i][j]

• 对于 b 1 ( y , w ) = ∑ i = 0 h − 1 w i b i ( 1 ) ( y ) b_1(y,w)=\sum_{i=0}^{h-1}w^ib_i^{(1)}(y) b1​(y,w)=∑i=0h−1​wibi(1)​(y)和 b 2 ( y , w ) = ∑ i = 0 h − 1 w i b i ( 2 ) ( y ) b_2(y,w)=\sum_{i=0}^{h-1}w^ib_i^{(2)}(y) b2​(y,w)=∑i=0h−1​wibi(2)​(y)，乘积为：
  b 1 ( y , w ) b 2 ( y , w ) = ∑ t = 0 h − 1 ∑ i = 0 h − 1 [ b t − i ( 1 ) ( y ) b i ( 2 ) ( y ) ] w t m o d    w h − 1 b_1(y,w)b_2(y,w) = \sum_{t=0}^{h-1}\sum_{i=0}^{h-1} [b_{t-i}^{(1)}(y) b_i^{(2)}(y)] w^t \mod{w^h-1} b1​(y,w)b2​(y,w)=t=0∑h−1​i=0∑h−1​[bt−i(1)​(y)bi(2)​(y)]wtmodwh−1

• 多项式乘积

  • 对于 a 1 , a 2 ∈ R [ x ] / ( x h ⋅ 2 k − 1 ) a_1,a_2 \in R[x]/(x^{h \cdot 2^k}-1) a1​,a2​∈R[x]/(xh⋅2k−1)，为了计算 a 1 ( x ) a 2 ( x ) a_1(x)a_2(x) a1​(x)a2​(x)，我们先得到 B 1 [ i ] [ j ] ,   B 2 [ i ] [ j ] B_1[i][j],\,B_2[i][j] B1​[i][j],B2​[i][j]
  • 阵列的第 j j j列，表示定点 y = ξ j y=\xi^j y=ξj处的关于 w w w的多项式： g y ( w ) = ∑ i = 0 h − 1 B 1 [ i ] [ j ] w i m o d    w h − 1 g_y(w) = \sum_{i=0}^{h-1}B_1[i][j]w^i \mod{w^h-1} gy​(w)=∑i=0h−1​B1​[i][j]wimodwh−1
  • 对 B 1 B_1 B1​和 B 2 B_2 B2​的第 j j j列做阵列乘，这等价于定点 y = ξ j y=\xi^j y=ξj处的多项式乘积 (循环卷积)： b 1 ( y , w ) b 2 ( y , w ) m o d    w n − 1 b_1(y,w)b_2(y,w) \mod{w^n-1} b1​(y,w)b2​(y,w)modwn−1
  • 最后，对结果阵列 B 3 B_3 B3​做并行的 h h h个INTT，得到 b 3 = b 1 b 2 b_3=b_1b_2 b3​=b1​b2​，并输出结果 a 3 = ϕ − 1 ( b 3 ) = a 1 a 2 a_3=\phi^{-1}(b_3) = a_1a_2 a3​=ϕ−1(b3​)=a1​a2​

• 复杂度： 2 h   O ( 2 k log ⁡ 2 k ) + 2 k   O ( h 2 ) = O ( 2 n log ⁡ n h ) + O ( n h ) 2h\,O(2^k\log 2^k) + 2^k\,O(h^2) = O(2n\log\dfrac{n}{h})+O(nh) 2hO(2klog2k)+2kO(h2)=O(2nloghn​)+O(nh)；当 h → 1 h \rightarrow 1 h→1时为 O ( n log ⁡ n ) O(n \log n) O(nlogn)，当 h → n h \rightarrow n h→n时为 O ( n 2 ) O(n^2) O(n2)

  也就是说，对于奇数 n n n，NTT对于 R [ x ] / ( x n − 1 ) R[x]/(x^n-1) R[x]/(xn−1)上的多项式乘积没有实质帮助？奥，我们可以模 x n ′ − 1 x^{n'}-1 xn′−1嘛，保证 n ′ > 2 n n'>2n n′>2n就行了。

环嵌入【模 q ≠ 2 k p ′ + 1 q \not = 2^kp'+1 q​=2kp′+1】

• 如果我们需要计算 Z q [ x ] / ( x n − 1 ) Z_q[x]/(x^n-1) Zq​[x]/(xn−1)上的多项式乘积，但是 n = 2 k ∤ q − 1 n=2^k \not \mid q-1 n=2k​∣q−1，即 q ≠ 2 k p ′ + 1 q \not = 2^kp'+1 q​=2kp′+1，于是 Z q Z_q Zq​中不存在n次本原单位根。
• 对于 f , g ∈ Z q [ x ] / ( x n − 1 ) f,g \in Z_q[x]/(x^n-1) f,g∈Zq​[x]/(xn−1)，令它们的系数范围是： f i ,   g i m o d     ± q ∈ [ − q 2 , q 2 ) f_i,\,g_i \mod {}^\pm q \in [-\dfrac{q}{2},\dfrac{q}{2}) fi​,gi​mod±q∈[−2q​,2q​)。容易知道，多项式乘积 f ( x ) g ( x ) f(x)g(x) f(x)g(x)的每一项的绝对值大小至多是 n q 2 4 \dfrac{nq^2}{4} 4nq2​
• 我们选取一个NTT友好的大素数 p > n q 2 2 p > \dfrac{nq^2}{2} p>2nq2​，满足 n ∣ p − 1 n \mid p-1 n∣p−1
• 我们把 f , g ∈ Z q [ x ] / ( x n − 1 ) f,g \in Z_q[x]/(x^n-1) f,g∈Zq​[x]/(xn−1)映射到 f ′ , g ′ ∈ Z p [ x ] / ( x n − 1 ) f',g' \in Z_p[x]/(x^n-1) f′,g′∈Zp​[x]/(xn−1)，这里就是简单的系数嵌入： ϕ : a ∈ Z p ↦ a ∈ Z q \phi:a \in Z_p \mapsto a \in Z_q ϕ:a∈Zp​↦a∈Zq​
• 将 f , g f,g f,g嵌入到 Z p [ x ] / ( x n − 1 ) Z_p[x]/(x^n-1) Zp​[x]/(xn−1)中得到 f ′ , g ′ f',g' f′,g′，计算多项式乘积，然后简单取模即可： f ( x ) g ( x ) ≡ f ′ ( x ) g ′ ( x ) m o d    q f(x)g(x) \equiv f'(x)g'(x) \mod{q} f(x)g(x)≡f′(x)g′(x)modq
• 由于 p > n q 2 2 p > \dfrac{nq^2}{2} p>2nq2​，因此乘积的系数不会模掉 p p p，所以上述结果一定正确。由于 n ∣ p − 1 n \mid p-1 n∣p−1，因此可以利用NTT加速多项式乘法。

多模数【模 q ≠ 2 k p ′ + 1 q \not = 2^kp'+1 q​=2kp′+1】

• 这是解决 n = 2 k ∤ q − 1 n=2^k \not \mid q-1 n=2k​∣q−1的另一种方案。

• 我们挑选一系列的NTT友好的小素数 { p j } \{p_j\} {pj​}，满足 n ∣ p j − 1 n \mid p_j-1 n∣pj​−1且 P = ∏ j p j > n q 2 2 P=\prod_j p_j > \dfrac{nq^2}{2} P=∏j​pj​>2nq2​

• 我们把 f , g ∈ Z q [ x ] / ( x n − 1 ) f,g \in Z_q[x]/(x^n-1) f,g∈Zq​[x]/(xn−1)映射到 f ′ , g ′ ∈ Z P [ x ] / ( x n − 1 ) f',g' \in Z_P[x]/(x^n-1) f′,g′∈ZP​[x]/(xn−1)，这里也是简单的系数嵌入。计算 f ′ ( x ) g ′ ( x ) m o d    q f'(x)g'(x)\mod{q} f′(x)g′(x)modq即可，且由于 P > n q 2 2 P > \dfrac{nq^2}{2} P>2nq2​，所以结果一定正确。

• 根据CRT，定义如下双射 (因为 g c d ( p i , p j ) = 1 gcd(p_i,p_j)=1 gcd(pi​,pj​)=1)：
  ϕ : f ′ m o d    P ↦ [ f ′ m o d    p 1 ,    ⋯   ,    f ′ m o d    p s ] \begin{aligned} \phi:f'\mod{P} \mapsto [f'\mod{p_1},\,\,\cdots,\,\,f'\mod{p_s}] \end{aligned} ϕ:f′modP↦[f′modp1​,⋯,f′modps​]​
  利用CRT的求解公式，当然是可以的；但有一种更高效的迭代算法。

  假设有同余方程组 u ≡ u i m o d    p i u \equiv u_i \mod{p_i} u≡ui​modpi​，且满足： ∣ u i ∣ < p i 2 ,   ∣ u ∣ < P 2 |u_i|<\dfrac{p_i}{2},\,|u|<\dfrac{P}{2} ∣ui​∣<2pi​​,∣u∣<2P​

  那么，
  y 1 = u 1 y 2 = y 1 + ( ( u 2 − y 1 ) m 2 m o d    ± p 2 ) ⋅ p 1 y 3 = y 2 + ( ( u 3 − y 2 ) m 3 m o d    ± p 3 ) ⋅ p 1 p 2 ⋮ y s = y s − 1 + ( ( u s − y s − 1 ) m s m o d    ± p s ) ⋅ p 1 p 2 ⋯ p s − 1 \begin{aligned} y_1 &= u_1\\ y_2 &= y_1 + ((u_2-y_1)m_2 \mod{{}^\pm p_2}) \cdot p_1\\ y_3 &= y_2 + ((u_3-y_2)m_3 \mod{{}^\pm p_3}) \cdot p_1p_2\\ & \vdots\\ y_s &= y_{s-1} + ((u_s-y_{s-1})m_s \mod{{}^\pm p_s}) \cdot p_1p_2\cdots p_{s-1}\\ \end{aligned} y1​y2​y3​ys​​=u1​=y1​+((u2​−y1​)m2​mod±p2​)⋅p1​=y2​+((u3​−y2​)m3​mod±p3​)⋅p1​p2​⋮=ys−1​+((us​−ys−1​)ms​mod±ps​)⋅p1​p2​⋯ps−1​​
  其中 m i : = ( p 1 p 2 ⋯ p i − 1 ) − 1 m o d    ± p i m_i:=(p_1p_2\cdots p_{i-1})^{-1} \mod{{}^\pm p_i} mi​:=(p1​p2​⋯pi−1​)−1mod±pi​，那么 u = y s u=y_s u=ys​

  算法结果正确，且对于小的 s s s，上述迭代算法比CRT更高效。

• 计算多项式乘法

  • 将 f , g f,g f,g嵌入到 Z p [ x ] / ( x n − 1 ) Z_p[x]/(x^n-1) Zp​[x]/(xn−1)中得到 f ′ , g ′ f',g' f′,g′
  • 做映射，得到 [ f i ′ ( x ) m o d    p i ] ,   [ g i ′ ( x ) m o d    p i ] [f'_i(x) \mod{p_i}],\,[g'_i(x) \mod{p_i}] [fi′​(x)modpi​],[gi′​(x)modpi​]
  • 对每个对应的分量，分别计算多项式乘积 (利用NTT)，得到序列 [ ( f ′ g ′ ) i ( x ) m o d    p i ] [(f'g')_i(x) \mod{p_i}] [(f′g′)i​(x)modpi​]
  • 求解方程组 ( f ′ g ′ ) ≡ ( f ′ g ′ ) i m o d    p i (f'g') \equiv (f'g')_i \mod{p_i} (f′g′)≡(f′g′)i​modpi​，最后 ( f g ) ≡ ( f ′ g ′ ) m o d    q (fg) \equiv (f'g') \mod{q} (fg)≡(f′g′)modq

总结

• 用快速数论变换 ( NTT) 实现时域、频域之间的快速转换。使用DFT的卷积性质，可加速 Z q [ x ] / ( x n − 1 ) Z_q[x]/(x^n-1) Zq​[x]/(xn−1)上多项式乘积的计算。时间复杂度： 2   O ( n log ⁡ n ) + O ( n ) = O ( n log ⁡ n ) 2\,O(n \log n)+O(n) = O(n \log n) 2O(nlogn)+O(n)=O(nlogn)
• 一、对于环 Z q [ x ] / ( x n − 1 ) ,   n ∣ q − 1 ,   n = 2 k Z_q[x]/(x^n-1),\, n \mid q-1,\, n=2^k Zq​[x]/(xn−1),n∣q−1,n=2k，用NTT可以直接求解。
• 二、对于环 Z q [ x ] / ( x n + 1 ) ,   n ∣ q − 1 ,   n = 2 k − 1 Z_q[x]/(x^n+1),\, n \mid q-1,\, n=2^{k-1} Zq​[x]/(xn+1),n∣q−1,n=2k−1，用Negacyclic NTT，做映射，在 Z q [ Y ] / ( Y n − 1 ) Z_q[Y]/(Y^n-1) Zq​[Y]/(Yn−1)上利用NTT求解。
• 三、对于环 Z q [ x ] / ( x n − 1 ) ,   n ∣ q − 1 ,   n = h ⋅ 2 k Z_q[x]/(x^n-1),\, n \mid q-1,\, n=h \cdot 2^k Zq​[x]/(xn−1),n∣q−1,n=h⋅2k，用Good’s Trick，将一元多项式映射为二元多项式 (以一元多项式为系数的一元多项式)，然后利用NTT求解。
• 四、对于环 Z q [ x ] / ( x n − 1 ) ,   n ∤ q − 1 ,   n = 2 k Z_q[x]/(x^n-1),\, n \not \mid q-1,\, n=2^k Zq​[x]/(xn−1),n​∣q−1,n=2k，用环嵌入，找到一个NTT友好的素数 n ∣ p − 1 n \mid p-1 n∣p−1，然后用NTT求解。
• 五、对于环 Z q [ x ] / ( x n − 1 ) ,   n ∤ q − 1 ,   n = 2 k Z_q[x]/(x^n-1),\, n \not \mid q-1,\, n=2^k Zq​[x]/(xn−1),n​∣q−1,n=2k，用多模数，找到一系列NTT友好的素数 n ∣ p i − 1 n \mid p_i-1 n∣pi​−1，然后用NTT分别求解，并用CRT组合结果。
• 六、对于环 Z q [ x ] / ( x n − 1 ) ,   n ∣ q − 1 ,   n = h Z_q[x]/(x^n-1),\, n \mid q-1,\, n=h Zq​[x]/(xn−1),n∣q−1,n=h，直接用Good’s Trick对多项式乘积没有帮助。我们可以寻找 n ′ = h × 2 k > 2 n n'=h \times 2^k > 2n n′=h×2k>2n，并寻找相应的 n ′ ∣ q ′ − 1 n' \mid q'-1 n′∣q′−1；然后在 Z q ′ [ x ] / ( x n ′ − 1 ) Z_{q'}[x]/(x^{n'}-1) Zq′​[x]/(xn′−1)上计算多项式乘积，最后结果 f g = ( f ′ g ′ ) m o d    q , x n − 1 fg = (f'g') \mod{q,x^n-1} fg=(f′g′)modq,xn−1即可。 要保证两个n长多项式一次相乘后不会模 x n ′ − 1 x^{n'}-1 xn′−1，以保证最终结果正确，所以要 n ′ > 2 n n' > 2n n′>2n
• 七、对于环 Z q [ x ] / ( x n − 1 ) ,   n ∤ q − 1 ,   n = h ⋅ 2 k Z_q[x]/(x^n-1),\, n \not \mid q-1,\, n=h \cdot 2^k Zq​[x]/(xn−1),n​∣q−1,n=h⋅2k，先用环嵌入或者多模数，使得 n ∣ p − 1 n \mid p-1 n∣p−1或者 n ∣ p i − 1 n \mid p_i-1 n∣pi​−1；这样问题就转化为了若干个问题“三”；用Good’s Trick，将一元多项式映射为二元多项式，然后利用NTT求解。
• 我们可以解决“六”和“七”，也就是说，对于任意的参数 q , n q,n q,n，环 Z q [ x ] / ( x n ± 1 ) Z_q[x]/(x^n \pm 1) Zq​[x]/(xn±1)上多项式乘积都可以用NTT快速计算。