快速数论变换

简介

数论变换(Number-theoretic transform, NTT)是 快速傅里叶变换(FFT)在数论基础上的实现。

NTT 解决的是多项式乘法带模数的情况,可以说有些受模数的限制,数也比较大,

定义

数论变换

数论变换 是一种计算卷积(convolution)的快速算法。最常用算法就包括了前文提到的快速傅里叶变换。然而快速傅立叶变换具有一些实现上的缺点,举例来说,资料向量必须乘上复数系数的矩阵加以处理,而且每个复数系数的实部和虚部是一个正弦及余弦函数,因此大部分的系数都是浮点数,也就是说,必须做复数而且是浮点数的运算,因此计算量会比较大,而且浮点数运算产生的误差会比较大。

在数学中,NTT 是关于任意 上的离散傅立叶变换(DFT)。在有限域的情况下,通常称为数论变换 (NTT)。

离散傅里叶变换

离散傅里叶变换(Discrete Fourier transform,DFT) 是傅里叶变换在时域和频域上都呈离散的形式,将信号的时域采样变换为其 DTFT 的频域采样。

对于 N 点序列 \left\{x[n]\right\}_{0\le n <N} ,它的离散傅里叶变换(DFT)为

\hat{x}[k]=\sum_{n=0}^{N-1} e^{-i\frac{2\pi}{N}nk}x[n] \qquad k = 0,1,\ldots,N-1.

其中 e 是自然对数的底数, i 是虚数单位。通常以符号 \mathcal {F} 表示这一变换,即

\hat{x}=\mathcal{F}x

它的 逆离散傅里叶变换(IDFT)为:

x\left[n\right]={1 \over N}\sum_{k=0}^{N-1} e^{ i\frac{2\pi}{N}nk}\hat{x}[k] \qquad n = 0,1,\ldots,N-1.

可以记为:

x=\mathcal{F}^{-1}\hat{x}

实际上,DFT 和 IDFT 变换式中和式前面的归一化系数并不重要。在上面的定义中,DFT 和 IDFT 前的系数分别为 1 \frac {1}{N} 。有时我们会将这两个系数都改 \frac {1}{{\sqrt {N}}}

矩阵公式

由于离散傅立叶变换是一个 线性 算子,所以它可以用矩阵乘法来描述。在矩阵表示法中,离散傅立叶变换表示如下:

{\displaystyle {\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{n-1}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(n-1)}\\\vdots &\vdots &\vdots &&\vdots \\1&\alpha ^{n-1}&\alpha ^{2(n-1)}&\cdots &\alpha ^{(n-1)(n-1)}\\\end{bmatrix}}{\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}.}

生成子群

子群:群 (S,⊕), (S′,⊕) ,满足 S′⊂S ,则 (S′,⊕) (S,⊕) 的子群

拉格朗日定理: |S′|∣|S | 证明需要用到陪集,得到陪集大小等于子群大小,每个陪集要么不相交要么相等,所有陪集的并是集合 S ,那么显然成立。

生成子群: a \in S 的生成子群 \left<a\right> = \{a^{(k)}, k \geq 1 \} a \left< a \right> 的生成元

阶:群 S a 的阶是满足 a^r=e 的最小的 r ,符号 \operatorname{ord}(a) ,有 \operatorname{ord}(a)=\left|\left<a\right>\right| ,显然成立。

考虑群 Z_n^ \times =\{[a], n \in Z_n : \gcd(a, n) = 1\}, |Z_n^ \times | = \varphi(n)

阶就是满足 a^r \equiv 1 \pmod n 的最小的 r \operatorname{ord}(a)=r

原根

g 满足 \operatorname{ord}_n(g)=\left|Z_n^\times\right|=\varphi(n) ,对于质数 p ,也就是说 g^i \bmod p, 0 \leq i < p 结果互不相同。

n 有原根的充要条件 : n = 2, 4, p^e, 2 \times p^e

离散对数: g^t \equiv a \pmod n,ind_{n,g}{(a)}=t

因为 g 是原根,所以 gt \varphi(n) 是一个周期,可以取到 | Z \times n | 的所有元素 对于 n 是质数时,就是得到 [1,n−1] 的所有数,就是 [0,n−2] [1,n−1] 的映射 离散对数满足对数的相关性质,如

求原根可以证明满足 g^r \equiv 1\pmod p 的最小的 r 一定是 p−1 的约数 对于质数 p ,质因子分解 p−1 ,若 g^{(p-1)/pi} \neq 1 \pmod p 恒成立, g p 的原根。

NTT

数论变换(NTT)是通过将离散傅立叶变换化为 F={\mathbb {Z}/p} ,整数模质数 p 。这是一个 有限域,只要 n 可除 p-1 ,就存在本元 n 次方根,所以我们有 p=\xi n+1 对于 a 正整数 ξ 。具体来说,对于质数 p=qn+1, (n=2^m) , 原根 g 满足 g^{qn} \equiv 1 \pmod p , 将 g_n=g^q\pmod p 看做 \omega_n 的等价,则其满足相似的性质,比如 g_n^n \equiv 1 \pmod p, g_n^{n/2} \equiv -1 \pmod p