兴国县城乡规划建设局网站怎么发帖子做推广

当前位置： 首页 > news >正文

兴国县城乡规划建设局网站,怎么发帖子做推广,网页微信版下载,1688网站建设方案书模板深入理解NTT 中国剩余定理 (CRT)#xff1a;环 R R R 上的有限个理想 { I i } {I_i} {Ii​}#xff0c;存在同态映射 σ : R / ⋂ i I i → ∏ i R / I i \sigma:R/\bigcap_i I_i \to \prod_i R/I_i σ:R/i⋂​Ii​→i∏​R/Ii​ 如果它们两两互素 I i I j R I_iI_jR…深入理解NTT 中国剩余定理 (CRT)环 R R R 上的有限个理想 { I i } {I_i} {Ii​}存在同态映射 σ : R / ⋂ i I i → ∏ i R / I i \sigma:R/\bigcap_i I_i \to \prod_i R/I_i σ:R/i⋂​Ii​→i∏​R/Ii​ 如果它们两两互素 I i I j R I_iI_jR Ii​Ij​R那么 σ \sigma σ 是环同构 在多项式环上如果 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)​ 环 Z q [ x ] / ( x n − 1 ) Z_q[x]/(x^n-1) Zq​[x]/(xn−1)其中 n 2 k , n ∣ q − 1 n2^k,\,n \mid q-1 n2k,n∣q−1取 ξ n ∈ Z q \xi_n \in Z_q ξn​∈Zq​ 容易验证如下分解等式 x n − 1 ( x n 2 − ξ n 0 ) ( x n 2 − ξ n n 2 ) x n 2 − ξ n 0 ( x n 4 − ξ n 0 ) ( x n 4 − ξ n 2 n 4 ) x n 2 − ξ n n 2 ( x n 4 − ξ n n 4 ) ( x n 4 − ξ n 3 n 4 ) ⋯ \begin{aligned} 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{aligned} xn−1x2n​−ξn0​x2n​−ξn2n​​⋯​(x2n​−ξn0​)(x2n​−ξn2n​​)(x4n​−ξn0​)(x4n​−ξn42n​​)(x4n​−ξn4n​​)(x4n​−ξn43n​​)​ 分解过程如图 j 0 j0 j0 j 1 j1 j1 j 2 j2 j2 x n 4 − ξ n 0 x^\frac{n}{4}-\xi_n^0 x4n​−ξn0​ ξ n 0 ( ξ n n 4 ) b r v 2 ( 0 ) \xi_n^0 (\xi_n^\frac{n}{4})^{brv_2(0)} ξn0​(ξn4n​​)brv2​(0) x n 2 − ξ n 0 x^\frac{n}{2}-\xi_n^0 x2n​−ξn0​ ξ n 0 ( ξ n n 2 ) b r v 1 ( 0 ) \xi_n^0 (\xi_n^\frac{n}{2})^{brv_1(0)} ξn0​(ξn2n​​)brv1​(0) x n 4 − ξ n 2 n 4 x^\frac{n}{4}-\xi_n^\frac{2n}{4} x4n​−ξn42n​​ ξ n 2 n 4 ( ξ n n 4 ) b r v 2 ( 1 ) \xi_n^\frac{2n}{4} (\xi_n^\frac{n}{4})^{brv_2(1)} ξn42n​​(ξn4n​​)brv2​(1) x n − 1 x n − ξ n 0 x^n-1 x^n-\xi_n^0 xn−1xn−ξn0​ x n 4 − ξ n n 4 x^\frac{n}{4}-\xi_n^\frac{n}{4} x4n​−ξn4n​​ ξ n n 4 ( ξ n n 4 ) b r v 2 ( 2 ) \xi_n^\frac{n}{4} (\xi_n^\frac{n}{4})^{brv_2(2)} ξn4n​​(ξn4n​​)brv2​(2) x n 2 − ξ n n 2 x^\frac{n}{2}-\xi_n^\frac{n}{2} x2n​−ξn2n​​ ξ n n 2 ( ξ n n 2 ) b r v 1 ( 1 ) \xi_n^\frac{n}{2} (\xi_n^\frac{n}{2})^{brv_1(1)} ξn2n​​(ξn2n​​)brv1​(1) x n 4 − ξ n 3 n 4 x^\frac{n}{4}-\xi_n^\frac{3n}{4} x4n​−ξn43n​​ ξ n 3 n 4 ( ξ n n 4 ) b r v 2 ( 3 ) \xi_n^\frac{3n}{4} (\xi_n^\frac{n}{4})^{brv_2(3)} ξn43n​​(ξn4n​​)brv2​(3) 令 f ( x ) ∈ Z q [ x ] / ( x n − 1 ) f(x) \in Zq[x]/(x^n-1) f(x)∈Zq​[x]/(xn−1)简记 f b 1 ⋯ b j ( x ) : f ( x ) m o d x n 2 j − ( ξ n n 2 j ) b r v j ( b 1 ⋯ b j ) f{b_1 \cdots b_j}(x) : f(x) \mod x^\frac{n}{2^j} - (\xi_n^\frac{n}{2^j})^{brv_j(b_1 \cdots b_j)} fb1​⋯bj​​(x):f(x)modx2jn​−(ξn2jn​​)brvj​(b1​⋯bj​)其中 b 1 ⋯ b j b_1 \cdots bj b1​⋯bj​是分解路径。 对应的位置关系如图 j 0 j0 j0 j 1 j1 j1 j 2 j2 j2 f 00 f ( x ) m o d x n 4 − ξ n 0 f{00} f(x) \mod x^\frac{n}{4}-\xin^0 f00​f(x)modx4n​−ξn0​ f 0 f ( x ) m o d x n 2 − ξ n 0 f{0} f(x) \mod x^\frac{n}{2}-\xin^0 f0​f(x)modx2n​−ξn0​ f 01 f ( x ) m o d x n 4 − ξ n 2 n 4 f{01} f(x) \mod x^\frac{n}{4}-\xin^\frac{2n}{4} f01​f(x)modx4n​−ξn42n​​ f f ( x ) m o d x n − 1 f f(x) \mod x^n-1 ff(x)modxn−1 f 10 f ( x ) m o d x n 4 − ξ n n 4 f{10} f(x) \mod x^\frac{n}{4}-\xin^\frac{n}{4} f10​f(x)modx4n​−ξn4n​​ f 1 f ( x ) m o d x n 2 − ξ n n 2 f{1} f(x) \mod x^\frac{n}{2}-\xin^\frac{n}{2} f1​f(x)modx2n​−ξn2n​​ f 11 f ( x ) m o d x n 4 − ξ n 3 n 4 f{11} f(x) \mod x^\frac{n}{4}-\xin^\frac{3n}{4} f11​f(x)modx4n​−ξn43n​​ 令阵列 f [ i ] f[i] f[i]是多项式 f ( x ) f(x) f(x)的系数向量即 f ( x ) ∑ i 0 n − 1 f [ i ] x i m o d x n − 1 f(x) \sum{i0}^{n-1} f[i] x^i \mod x^n-1 f(x)i0∑n−1​f[i]ximodxn−1 模掉 x n 2 − a x^\frac{n}{2} - a x2n​−a为 f ( x ) ∑ i 0 n 2 − 1 ( f [ i ] a f [ i n 2 ] ) x i m o d x n 2 − a f(x) \sum{i0}^{\frac{n}{2}-1} (f[i] af[i \frac{n}{2}]) x^i \mod x^\frac{n}{2} - a f(x)i0∑2n​−1​(f[i]af[i2n​])ximodx2n​−a 令阵列 f 0 [ i ] f{0}[i] f0​[i]是多项式 f 0 ( x ) f{0}(x) f0​(x)的系数向量阵列 f 1 [ i ] f{1}[i] f1​[i]是多项式 f 1 ( x ) f_{1}(x) f1​(x)的系数向量那么 f 0 ( x ) ∑ i 0 n 2 − 1 ( f [ i ] ξ n 0 f [ i n 2 ] ) x i m o d x n 2 − ξ n 0 f 1 ( x ) ∑ i 0 n 2 − 1 ( f [ i ] ξ n n 2 f [ i n 2 ] ) x i m o d x n 2 − ξ n n 2 \begin{aligned} f0(x) \sum{i0}^{\frac{n}{2}-1} (f[i] \xi_n^0 f[i \frac{n}{2}]) x^i \mod x^\frac{n}{2} - \xi_n^0\ f1(x) \sum{i0}^{\frac{n}{2}-1} (f[i] \xi_n^\frac{n}{2} f[i \frac{n}{2}]) x^i \mod x^\frac{n}{2} - \xi_n^\frac{n}{2}\ \end{aligned} f0​(x)i0∑2n​−1​(f[i]ξn0​f[i2n​])ximodx2n​−ξn0​f1​(x)i0∑2n​−1​(f[i]ξn2n​​f[i2n​])ximodx2n​−ξn2n​​​ 其中 ξ n n 2 − ξ n 0 \xi_n^\frac{n}{2} -\xin^0 ξn2n​​−ξn0​后续的分解类似。 使用CT蝴蝶 f b 1 ⋯ b j − 1 [ i ] → → → → → ⊕ → f b 1 ⋯ b j − 1 ∣ 0 [ i ] ↘ ↗ ⋅ ↗ ↘ f b 1 ⋯ b j − 1 [ i n 2 ] → ⊗ → → → ⊖ → f b 1 ⋯ b j − 1 ∣ 1 [ i ] ↑ ( ξ n n 2 j ) b r v ( b 1 ⋯ b j − 1 ∣ 0 ) \begin{matrix} f{b1 \cdots b{j-1}}[i] \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \oplus \rightarrow f_{b1 \cdots b{j-1} |0}[i]\ \searrow \nearrow\ \cdot\ \nearrow \searrow\ f_{b1 \cdots b{j-1}}[i\frac{n}{2}] \rightarrow \otimes \rightarrow \rightarrow \rightarrow \ominus \rightarrow f_{b1 \cdots b{j-1} |1}[i]\ \uparrow\ (\xi_n^{\frac{n}{2^{j}}})^{brv(b1 \cdots b{j-1}|0)}\ \end{matrix} fb1​⋯bj−1​​[i]fb1​⋯bj−1​​[i2n​]​→→​→⊗↑(ξn2jn​​)brv(b1​⋯bj−1​∣0)​→↘↗→​→⋅→​→↗↘→​⊕⊖​→→​fb1​⋯bj−1​∣0​[i]fb1​⋯bj−1​∣1​[i]​ 阵列的迭代流程如下图所示 j 0 j0 j0 j 1 j1 j1 j 2 j2 j2 f [ 0 ] f[0] f[0] f 0 [ 0 ] f0[0] f0​[0] f 00 [ 0 ] f{00}[0] f00​[0] ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ f 0 [ n 4 − 1 ] f0[\frac{n}{4} - 1] f0​[4n​−1] f 00 [ n 4 − 1 ] f{00}[\frac{n}{4} - 1] f00​[4n​−1] ⋮ \vdots ⋮ f 0 [ n 4 ] f0[\frac{n}{4}] f0​[4n​] f 01 [ 0 ] f{01}[0] f01​[0] ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ f [ n 2 − 1 ] f[\frac{n}{2} - 1] f[2n​−1] f 0 [ n 2 − 1 ] f0[\frac{n}{2} - 1] f0​[2n​−1] f 01 [ n 4 − 1 ] f{01}[\frac{n}{4} - 1] f01​[4n​−1] f [ n 2 ] f[\frac{n}{2}] f[2n​] f 1 [ 0 ] f1[0] f1​[0] f 10 [ 0 ] f{10}[0] f10​[0] ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ f 1 [ n 4 − 1 ] f1[\frac{n}{4} - 1] f1​[4n​−1] f 10 [ n 4 − 1 ] f{10}[\frac{n}{4} - 1] f10​[4n​−1] ⋮ \vdots ⋮ f 1 [ n 4 ] f1[\frac{n}{4}] f1​[4n​] f 11 [ 0 ] f{11}[0] f11​[0] ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ f [ n − 1 ] f[n - 1] f[n−1] f 1 [ n 4 − 1 ] f1[\frac{n}{4} - 1] f1​[4n​−1] f 11 [ n 4 − 1 ] f{11}[\frac{n}{4} - 1] f11​[4n​−1]即使用CT蝴蝶将阵列 f [ i ] f[i] f[i]迭代运算 j j j次将会得到 2 j 2^j 2j个多项式它们是 f ( x ) m o d x 2 k − j − ξ j i f(x) \mod x^{2^{k-j}} - \xi{ji} f(x)modx2k−j−ξji​这里的 ξ j i ( ξ n n 2 j ) b r v j ( b 1 ⋯ b j ) \xi{ji} (\xi_n^\frac{n}{2^j})^{brv_j(b_1 \cdots b_j)} ξji​(ξn2jn​​)brvj​(b1​⋯bj​)代表第 j j j列、第 i d e c ( b 1 ⋯ b j ) i dec(b_1 \cdots b_j) idec(b1​⋯bj​)行的模多项式的常数项。 如果迭代 k k k次将会得到 2 k 2^k 2k个多项式它们就是 f ( ξ n b r v ( i ) ) f ( x ) m o d x − ξ n b r v ( i ) f(\xi_n^{brv(i)}) f(x) \mod x - \xin^{brv(i)} f(ξnbrv(i)​)f(x)modx−ξnbrv(i)​ f ( x ) f(x) f(x)的 2 k 2^k 2k个key-value pair 根据以上分析我们使用CT蝴蝶迭代没必要迭代到最后一层。将 f f f分解为若干 f m o d x h − ξ j i f \mod x^h-\xi{ji} fmodxh−ξji​即可这便是不完全NTT了。 由于 f b 1 ⋯ b j − 1 ∣ 0 [ i ] f b 1 ⋯ b j − 1 i b r v ( b 1 ⋯ b j − 1 ∣ 0 ) f b 1 ⋯ b j − 1 [ i n 2 ] f b 1 ⋯ b j − 1 ∣ 1 [ i ] f b 1 ⋯ b j − 1 [ i ] − ( ξ n n 2 j ) b r v ( b 1 ⋯ b j − 1 ∣ 0 ) f b 1 ⋯ b j − 1 [ i n 2 ] \begin{aligned} f_{b1 \cdots b{j-1} |0}[i] f_{b1 \cdots b{j-1}}i^{brv(b1 \cdots b{j-1}|0)} f_{b1 \cdots b{j-1}}[i\frac{n}{2}]\ f_{b1 \cdots b{j-1} |1}[i] f_{b1 \cdots b{j-1}}[i] - (\xi_n^{\frac{n}{2^{j}}})^{brv(b1 \cdots b{j-1}|0)} f_{b1 \cdots b{j-1}}[i\frac{n}{2}]\ \end{aligned} fb1​⋯bj−1​∣0​[i]fb1​⋯bj−1​​ibrv(b1​⋯bj−1​∣0)fb1​⋯bj−1​​[i2n​]fb1​⋯bj−1​∣1​[i]fb1​⋯bj−1​​[i]−(ξn2jn​​)brv(b1​⋯bj−1​∣0)fb1​⋯bj−1​​[i2n​]​ 那么 f b 1 ⋯ b j − 1 [ i ] f b 1 ⋯ b j − 1 ∣ 0 [ i ] f b 1 ⋯ b j − 1 ∣ 1 [ i n 2 ] 2 f b 1 ⋯ b j − 1 [ i n 2 ] f b 1 ⋯ b j − 1 ∣ 0 [ i ] − f b 1 ⋯ b j − 1 ∣ 1 [ i n 2 ] 2 ⋅ ( ξ n n 2 j ) b r v ( b 1 ⋯ b j − 1 ∣ 0 ) \begin{aligned} f_{b1 \cdots b{j-1}}[i] \frac{f_{b1 \cdots b{j-1} |0}[i] f_{b1 \cdots b{j-1} |1}[i\frac{n}{2}]}{2}\ f_{b1 \cdots b{j-1}}[i\frac{n}{2}] \frac{f_{b1 \cdots b{j-1} |0}[i] - f_{b1 \cdots b{j-1} |1}[i\frac{n}{2}]}{2 \cdot (\xi_n^{\frac{n}{2^{j}}})^{brv(b1 \cdots b{j-1}|0)} }\ \end{aligned} fb1​⋯bj−1​​[i]fb1​⋯bj−1​​[i2n​]​2fb1​⋯bj−1​∣0​[i]fb1​⋯bj−1​∣1​[i2n​]​2⋅(ξn2jn​​)brv(b1​⋯bj−1​∣0)fb1​⋯bj−1​∣0​[i]−fb1​⋯bj−1​∣1​[i2n​]​​ 使用GS蝴蝶来进行INTT 2 ⋅ f b 1 ⋯ b j − 1 [ i ] ← ← ← ⊕ ← ← ← f b 1 ⋯ b j − 1 ∣ 0 [ i ] ↖ ↙ ⋅ ↙ ↖ 2 ⋅ f b 1 ⋯ b j − 1 [ i n 2 ] ← ⊗ ← ⊖ ← ← ← f b 1 ⋯ b j − 1 ∣ 1 [ i ] ↑ 1 ( ξ n n 2 j ) b r v ( b 1 ⋯ b j − 1 ∣ 0 ) \begin{matrix} 2 \cdot f_{b1 \cdots b{j-1}}[i] \leftarrow \leftarrow \leftarrow \oplus \leftarrow \leftarrow \leftarrow f_{b1 \cdots b{j-1} |0}[i]\ \nwarrow \swarrow\ \cdot\ \swarrow \nwarrow\ 2 \cdot f_{b1 \cdots b{j-1}}[i\frac{n}{2}] \leftarrow \otimes \leftarrow \ominus \leftarrow \leftarrow \leftarrow f_{b1 \cdots b{j-1} |1}[i]\ \uparrow\ \dfrac{1}{(\xi_n^{\frac{n}{2^{j}}})^{brv(b1 \cdots b{j-1}|0)}}\ \end{matrix} 2⋅fb1​⋯bj−1​​[i]2⋅fb1​⋯bj−1​​[i2n​]​←←​←⊗↑(ξn2jn​​)brv(b1​⋯bj−1​∣0)1​​←←​⊕⊖​←↖↙←​←⋅←​←↙↖←​fb1​⋯bj−1​∣0​[i]fb1​⋯bj−1​∣1​[i]​ 从第 j j j层使用GS蝴蝶做INTT迭代 j j j次后将得到阵列 f ′ [ i ] 2 j f [ i ] m o d q f[i] 2^j f[i] \mod q f′[i]2jf[i]modq 容易恢复多项式 f ( x ) ⟺ f ′ [ i ] ⋅ ( 2 j ) − 1 m o d q f(x) \iff f[i] \cdot (2^j)^{-1} \mod q f(x)⟺f′[i]⋅(2j)−1modq
总结 FFT迭代的每一步都是利用CRT Z q [ x ] / ( x n − ξ ) ≅ Z q [ x ] / ( x n / 2 − ξ ′ ) × Z q [ x ] / ( x n / 2 − ξ ′ ′ ) Z_q[x]/(x^n - \xi) \cong Z_q[x]/(x^{n/2} - \xi) \times Zq[x]/(x^{n/2} - \xi) Zq​[x]/(xn−ξ)≅Zq​[x]/(xn/2−ξ′)×Zq​[x]/(xn/2−ξ′′) 将 f m o d x n − ξ f \mod x^n-\xi fmodxn−ξ 分解为 f m o d x n / 2 − ξ ′ , f m o d x n / 2 − ξ ′ ′ f \mod x^{n/2} - \xi,\,f \mod x^{n/2} - \xi fmodxn/2−ξ′,fmodxn/2−ξ′′其中 x n − ξ ( x n / 2 − ξ ′ ) ( x n / 2 − ξ ′ ′ ) x^n - \xi (x^{n/2} - \xi)(x^{n/2} - \xi) xn−ξ(xn/2−ξ′)(xn/2−ξ′′) 迭代 j j j次后所得结果是 2 j 2^j 2j个多项式 f b i n j ( i ) f m o d x n / 2 j − ξ j i , i 0 , 1 , ⋯ , 2 j − 1 f{binj(i)} f \mod x^{n/2^j} - \xi{ji},\, i0,1,\cdots,2^j-1 fbinj​(i)​fmodxn/2j−ξji​,i0,1,⋯,2j−1 用CT蝴蝶实现FFT用GS蝴蝶实现IFFT 假设 f ( 1 ) , f ( 2 ) f^{(1)},\, f^{(2)} f(1),f(2)在第 j j j层的分解是 f b i n j ( i ) ( 1 ) , f b i n j ( i ) ( 2 ) f_{binj(i)}^{(1)},\, f{binj(i)}^{(2)} fbinj​(i)(1)​,fbinj​(i)(2)​那么 f ( 1 ) ⋅ f ( 2 ) ⟺ f b i n j ( i ) ( 1 ) ⋅ f b i n j ( i ) ( 2 ) f^{(1)} \cdot f^{(2)} \iff f{binj(i)}^{(1)} \cdot f{bin_j(i)}^{(2)} f(1)⋅f(2)⟺fbinj​(i)(1)​⋅fbinj​(i)(2)​左右都是卷积。 如果 j k jk jk那么 f ( 1 ) ⋅ f ( 2 ) ⟺ f ( 1 ) ( ξ i ) ⋅ f ( 2 ) ( ( ξ i ) ) f^{(1)} \cdot f^{(2)} \iff f^{(1)}(\xi^i) \cdot f^{(2)}((\xi^i)) f(1)⋅f(2)⟺f(1)(ξi)⋅f(2)((ξi))右边退化为阵列乘积。