NTT负包裹卷积

前言

本博客的Markdown文件下载地址：https://download.csdn.net/download/wxkhturfun/87134519

一. 数学公式

$g$是原根，$p$是模数，即在模$p$的整数环下运算，$N$是多项式长度($N$是2的整数次幂)

数论变换（NTT）：

1. 式1：$X_k={\sum }_{n=0}^{N-1}{x}_n{G}_N^{nk}modp$，其中记$G_N=g^{\frac{p-1}{N}}\mathrm{mod}p$

数论变换逆变换（INTT）：

2. 式2：$x_n=\frac{1}{N}{\sum }_{k=0}^{N-1}{X}_k{G}_N^{-nk}modp$

模$p$下求逆：

对正整数$a$来讲，在模$p$下有$a^{{p-1}\equiv a}{p-2}\cdot a\equiv1\ mod\ p $，故要求$a$的倒数则可通过$a\equiv\frac{1}{a^{p-2}}\ mod\ p$来求得

所以INTT也可以写为：

3. 式3：$x_n=N^{p-2}{\sum }_{k=0}^{N-1}{X}_k{G}_N^{nk(p-2)}modp$

补充数学性质：

性质1： $G_N^{k+\frac{N}{2}}=-G_N^k$

性质2： $(G_N^k{)}^2=G_{N/2}^k$

性质3： ${\sum }_{i=0}^{N-1}(G_N^k{)}^i=0\mathrm{mod}p$

性质4： $G_N^m\ne G_N^n,(0\le m，n<N-1，且m\ne n)$

二. 负包裹卷积

不使用负包裹卷积举例：计算$\vec{a}$与$\vec{b}$相乘在$\mathbb{Z}/(x^n+1)$下的结果$\vec{c}$，这里我们取$n=4$

1. a ⃗ = { 1 , 2 , 3 , 4 } \vec{a}=\{1,2,3,4\} a ={1,2,3,4}， b ⃗ = { 1 , 2 , 3 , 4 } \vec{b}=\{1,2,3,4\} b ={1,2,3,4}
2. 则$\vec{c}=1+4x+10x^2+20x^3+25x^4+24x^5+16x^6$
3. 由于$n=4$，故需要模$x^4+1$
4. $\vec{c}=(\frac{1+4x+10x^2+20x^3}{正数部分}+\frac{25x^4+24x^5+16x^6}{超过x^4+1,所以是负数部分})/(x^4+1)=-24-20x-6x^2+20x^3$

负包裹卷积流程：

多项式 a ⃗ = { a 0 , a 1 , ⋅ ⋅ ⋅ , a n − 1 } \vec{a}=\{a_0,a_1,\cdot\cdot\cdot,a_{n-1}\} a ={a0​,a1​,⋅⋅⋅,an−1​}与多项式 b ⃗ = { b 0 , b 1 , ⋅ ⋅ ⋅ , b n − 1 } \vec{b}=\{b_0,b_1,\cdot\cdot\cdot, b_{n-1}\} b ={b0​,b1​,⋅⋅⋅,bn−1​}进行负包裹卷积运算

1. 令$\phi =G_{2N}=g^{\frac{p-1}{2N}}$
2. 令 a ′ = { a 0 , a 1 φ , ⋅ ⋅ ⋅ , φ n − 1 a n − 1 } a'=\{a_0,a_1\varphi,\cdot\cdot\cdot,\varphi^{n-1} a_{n-1}\} a′={a0​,a1​φ,⋅⋅⋅,φn−1an−1​}，令 b ′ = { b 0 , b 1 φ , ⋅ ⋅ ⋅ , φ n − 1 b n − 1 } b'=\{b_0,b_1\varphi,\cdot\cdot\cdot,\varphi^{n-1} b_{n-1}\} b′={b0​,b1​φ,⋅⋅⋅,φn−1bn−1​}
3. NTT：记$A=NTT(a^{\prime })$，$B=NTT(b^{\prime })$
4. 逐点乘法(point wise multiplication)：$C=A\circ B$
5. INTT： c ′ = I N T T ( C ) = { c 0 , φ c 1 , . . . , φ n − 1 c n − 1 } c'=INTT(C)=\{c_0,\varphi c_1,...,\varphi^{n-1} c_{n-1}\} c′=INTT(C)={c0​,φc1​,...,φn−1cn−1​}
6. 把$\phi$因子再去掉，得到最终结果 c ⃗ = { c 0 , φ − 1 c 1 , . . . , φ − ( n − 1 ) c n − 1 } \vec{c}=\{c_0,\varphi^{-1}c_1,...,\varphi^{-(n-1)}c_{n-1}\} c ={c0​,φ−1c1​,...,φ−(n−1)cn−1​}

三. 负包裹卷积举例

输入： a ⃗ = { a 0 , a 1 } \vec{a}=\{a_0,a_1\} a ={a0​,a1​}， b ⃗ = { b 0 , b 1 } \vec{b}=\{b_0,b_1\} b ={b0​,b1​}，这里$N=2$

可根据链接：https://fanfansann.blog.csdn.net/article/details/115732914，选择原根与选择模数

以下严格按照负包裹卷积步骤：

1. 令$\phi =G_{2N}=g^{\frac{p-1}{2N}}$

2. a ′ = { a 0 , a 1 φ } a'=\{a_0,a_1\varphi\} a′={a0​,a1​φ}， b ′ = { b 0 , b 1 φ } b'=\{b_0,b_1\varphi\} b′={b0​,b1​φ}

3. $NTT(a^{\prime })\Rightarrow A_k=a_0+a_1\phi G_N^k$

   $NTT(b^{\prime })\Rightarrow B_k=b_0+b_1\phi G_N^k$

   则有：
   $$\begin{gathered} A_0=a_0+a_1\phi \\ {A}_1=a_0+a_1\phi G_2^1 \\ {B}_0=b_0+b1\phi \\ {B}_1=b0+b_1\phi G_2^1 \end{gathered}$$

4. 逐点乘法：$C_k=A_k\circ B_k$

   则有：

   1. $C_0=A_0\cdot B_0=a_0{b}_0+(a_0{b}_1+a_1{b}_0)\phi +a_1{b}_1{\phi }^2$

   2. $C_1=A_1\cdot B_1=a_0{b}_0-(a_0{b}_1+a_1{b}_0)\phi +a_1{b}_1{\phi }^2$

      原因如下：

      $C_1=A_1\cdot B_1=a_0{b}_0+(a_0{b}_1+a_1{b}_0)\phi G_2^1+a_1{b}_1{\phi }^2{G}_2^2$

      由于$G_2^1=-1$，$G_2^2=1$(有严格的数学证明)

      故$C_1=A_1\cdot B_1=a_0{b}_0-(a_0{b}_1+a_1{b}_0)\phi +a_1{b}_1{\phi }^2$

5. INTT：$c^{\prime }=INTT(C)\Rightarrow c_n=\frac{1}{N}(C_0+C_1{G}_N^{-k})=\frac{1}{N}(A_0{B}_0+A_1{B}_1{G}_N^{-k})$

   1. $c_0=\frac{1}{2}[a_0{b}_0(1+1)+(a_0{b}_1+a_1{b}_0)\phi (1-1)+a_1{b}_1{\phi }^2(1+1)]=a_0{b}_0+a_1{b}_1{\phi }^2$
   2. $c_1=\frac{1}{2}[a_0{b}_0(1-1)+2(a_0{b}_1+a_1{b}_0)\phi +a_1{b}_1{\phi }^2(1-1)]=(a_0{b}_1+a_1{b}_0)\phi$

   所以 c ′ = { c 0 , c 1 } = { a 0 b 0 + a 1 b 1 φ 2     ,     ( a 0 b 1 + a 1 b 0 ) φ } c'=\{c_0,c_1\}=\{a_0b_0+a_1b_1\varphi^2\ \ \ ,\ \ \ (a_0b_1+a_1b_0)\varphi\} c′={c0​,c1​}={a0​b0​+a1​b1​φ2   ,   (a0​b1​+a1​b0​)φ}

6. 把$\phi$因子去除： c ⃗ = { c 0 , c 1 } = { a 0 b 0 + a 1 b 1 φ 2     ,     ( a 0 b 1 + a 1 b 0 ) } \vec{c}=\{c_0,c_1\}=\{a_0b_0+a_1b_1\varphi^2\ \ \ ,\ \ \ (a_0b_1+a_1b_0)\} c ={c0​,c1​}={a0​b0​+a1​b1​φ2   ,   (a0​b1​+a1​b0​)}，由于$\phi =G_{2N}=g^{\frac{p-1}{2N}}$，故${\phi }^2=g^{\frac{2\ast (p-1)}{2\ast N}}=-1$，所以有：

   c ⃗ = { c 0 , c 1 } = { a 0 b 0 − a 1 b 1     ,     ( a 0 b 1 + a 1 b 0 ) } \vec{c}=\{c_0,c_1\}=\{a_0b_0-a_1b_1\ \ \ ,\ \ \ (a_0b_1+a_1b_0)\} c ={c0​,c1​}={a0​b0​−a1​b1​   ,   (a0​b1​+a1​b0​)}

四. 结果分析

倘若直接将 a ⃗ = { a 0 , a 1 } \vec{a}=\{a_0,a_1\} a ={a0​,a1​}， b ⃗ = { b 0 , b 1 } \vec{b}=\{b_0,b_1\} b ={b0​,b1​}相乘，然后再模运算会怎么样呢：$\vec{a}\cdot \vec{b}/(x^2+1)$

$\vec{a}\cdot \vec{b}/(x^2+1)=[a_0{b}_0+(a_0{b}_1+a_1{b}_0)x+a_1{b}_1{x}^2]/(x^2+1)=a_0{b}_0+(a_0{b}_1+a_1{b}_0)x-a_1{b}_1=a_0{b}_0-a_1{b}_1+(a_0{b}_1+a_1{b}_0)x$

结果与负包裹卷积相同。