数论变换相关整理

常用模数


p = 998244353 = 7 × 17 × 2 23 + 1 , g = 3 p = 1004535809 = 479 × 2 21 + 1 , g = 3 \begin{aligned}&p=998244353=7\times17\times2^{23}+1&,g=3\\&p=1004535809=479\times2^{21}+1&,g=3\end{aligned} p=998244353=7×17×223+1p=1004535809=479×221+1,g=3,g=3


可能用到的模数


p                   r   k   g
------------------------------
3                   1   1   2
5                   1   2   2
17                  1   4   3
97                  3   5   5
193                 3   6   5
257                 1   8   3
7681                15  9   17
12289               3   12  11
40961               5   13  3
65537               1   16  3
786433              3   18  10
5767169             11  19  3
7340033             7   20  3
23068673            11  21  3
104857601           25  22  3
167772161           5   25  3
469762049           7   26  3
998244353           119 23  3
1004535809          479 21  3
2013265921          15  27  31
2281701377          17  27  3
3221225473          3   30  5
75161927681         35  31  3
77309411329         9   33  7
206158430209        3   36  22
2061584302081       15  37  7
2748779069441       5   39  3
6597069766657       3   41  5
39582418599937      9   42  5
79164837199873      9   43  5
263882790666241     15  44  7
1231453023109121    35  45  3
1337006139375617    19  46  3
3799912185593857    27  47  5
4222124650659841    15  48  19
7881299347898369    7   50  6
31525197391593473   7   52  3
180143985094819841  5   55  6
1945555039024054273 27  56  5
4179340454199820289 29  57  3

  对于上表中出现的数字,都有 p p p 是一个质数,且 p = r × 2 k + 1 p=r\times2^k+1 p=r×2k+1 g g g p p p 的阶等于 φ ( p ) \varphi(p) φ(p)

  表中部分模数 摘自此


  前置知识 快速傅里叶变换


Number-theoretic transform

  • 数论变换
  • 快速数论变换
    • 预备知识
    • NTT


数论变换

Number-theoretic transform


  数论变换是一种快速计算卷积的算法,虽然我们都知道,计算卷积的快速算法,最常用的就是傅里叶变换。

  但傅里叶变换有着目前计算机无法忽视的缺点:

  速度、精度。

  一个参与傅里叶变换的多项式,每一项系数都要转换为浮点型的复数,乘上一个复数矩阵,而每一个复数的实部虚部都是一个余弦正弦函数,庞大的浮点数计算量带来了误差和时耗。

  而数论变换是在整数上的变化,只会将参与变化的多项式原原本本的乘上一个整数矩阵,不过最终的结果会是卷积模上一个指定的整数,这与能处理任何复数的傅里叶变换不同,

  在信奥赛中,我们通常使用快速数论变换 ( N T T \mathrm{NTT} NTT) 来加速带模数的多项式乘法。


  定义多项式 f ( x ) f(x) f(x) x i x^i xi 项上的系数为 f [ i ] = a i f[i]=a_i f[i]=ai,度数为 N − 1 N - 1 N1,则对 f f f p p p N T T \mathrm{NTT} NTT 为: F ( x )   ∣   F [ k ] = ∑ n = 0 N − 1 f [ n ] α n k ( m o d p ) k = 0 , 1 , 2 , ⋯   , N F(x)\ |\ F[k]=\sum_{n=0}^{N-1}f[n]\alpha^{nk} \pmod p\quad k=0,1,2,\cdots,N F(x)  F[k]=n=0N1f[n]αnk(modp)k=0,1,2,,N  而对 F F F 的逆数论变换为: f ( x )   ∣   f [ k ] = N − 1 ∑ n = 0 N − 1 F [ n ] α − n k ( m o d p ) k = 0 , 1 , 2 , ⋯   , N f(x)\ |\ f[k]=N^{-1}\sum_{n=0}^{N-1}F[n]\alpha^{-nk} \pmod p\quad k=0,1,2,\cdots,N f(x)  f[k]=N1n=0N1F[n]αnk(modp)k=0,1,2,,N  这与 D F T \mathrm{DFT} DFT 形式。


快速数论变换


  在复数上,我们通过单位根的性质可以做到快速傅里叶变换,而在群上,同样有一种神奇的数字。


预备知识

getting started


group


  在数学中,群是由一个集合 G G G 以及一个二元关系 ⋅ \cdot 组成的代数结构,且满足:

  封闭性:若有 a , b ∈ G a,b\in G a,bG,则 a , b a,b a,b 满足 a ⋅ b ∈ G a\cdot b\in G abG
  结合律:若有 a , b , c ∈ G a,b,c\in G a,b,cG,则 ( a ⋅ b ) ⋅ c = a ⋅ ( b ⋅ c ) (a\cdot b)\cdot c = a\cdot (b\cdot c) (ab)c=a(bc)
  单位元 G G G 中存在一个元素 e e e,对 G G G 中的每一个元素 a a a 都有 e ⋅ a = a ⋅ e = a e\cdot a = a\cdot e = a ea=ae=a
  逆元:对 G G G 中的每一个元素 a a a,总存在一个元素 b b b,满足 a ⋅ b = b ⋅ a = e a\cdot b = b\cdot a = e ab=ba=e

  则我们称 ( G , ⋅ ) (G,\cdot) (G,) 为一个群,比如整数集 Z \mathbb Z Z 与加法 + + + 构成一个群。

  而我们熟悉的 a a a n n n 的乘法逆元,就是集合 Z n = { a ∣ gcd ⁡ ( a , n ) = 1 } \mathbb Z_n = \{a|\gcd(a,n)=1\} Zn={agcd(a,n)=1} 构成的群 ( Z n , × ) (\mathbb Z_n,\times) (Zn,×) a a a 的逆元。


order


  在群 G G G 上, a a a 的阶指的是一个最小的正整数 d d d d d d 满足 x d = e x^d = e xd=e,记为 ord ⁡ G ( a ) = d \operatorname{ord}_G(a)=d ordG(a)=d


原根

primitive root


  若群 G G G 存在元素 g g g,使得 ord ⁡ n ( g ) = ∣ G ∣ \operatorname{ord}_n(g)=|G| ordn(g)=G,则称 g g g G G G 的一个原根。

  对于群 Z p × = ( Z , × ( m o d p ) ) \mathbb Z_{p}^\times = (\mathbb Z,\times\pmod p) Zp×=(Z,×(modp)) p p p 为质数,设 g g g Z p × \mathbb Z_{p}^\times Zp× 的一个原根,则 g i ≡ 1 ( m o d 1 ) g^i \equiv 1 \pmod 1 gi1(mod1) 只在 i = p − 1 i = p - 1 i=p1 时成立。

  而 g i mod ⁡ p g^i\operatorname{mod} p gimodp 0 < i < p 0 < i < p 0<i<p 的结果各不相同。

  略证:

  若存在 0 < j < i 0 < j < i 0<j<i 使得 g j = g i g^j = g^i gj=gi,则 g p − 1 − i + j ≡ 1 ( m o d p ) g^{p-1-i+j} \equiv 1\pmod p gp1i+j1(modp),与原根定义相悖。 □ \square


原根的性质


  令 n = 2 n ′ n = 2^{n'} n=2n n ′ > 0 n' > 0 n>0 n ∣ ( p − 1 ) n |(p-1) n(p1)

  令 g n = g p − 1 n g_n = g^{\frac{p-1}n} gn=gnp1,我们会发现, g n g_n gn 上具备一些单位根的性质,而这正是我们快速数论变换所需要的。

   g n 0 = g n n = 1 g_n^0 = g_n^n = 1 gn0=gnn=1

   g 2 n n + k = − g 2 n k g_{2n}^{n+k} = -g_{2n}^k g2nn+k=g2nk

   g 2 n 2 k = g n k g_{2n}^{2k} = g_n^k g2n2k=gnk

  同样简单推算一下式 2 2 2

   g 2 n n + k = g 2 n n g 2 n k g_{2n}^{n+k} = g_{2n}^ng_{2n}^k g2nn+k=g2nng2nk g 2 n n = g p − 1 2 = − 1 g_{2n}^n = g^{\frac{p-1}2}=-1 g2nn=g2p1=1 g 2 n n + k = − g 2 n k g_{2n}^{n+k} = -g_{2n}^k g2nn+k=g2nk

  中间式子涉及到一个非平凡平方根的概念,笔者在 这篇博客 中有简单提到过,当然也可以继续从原根的定义出发,去推导、理解它。


NTT


  至此,我们发现,小改一下 F F T \mathrm{FFT} FFT 的模板,就能实现快速 N T T \mathrm{NTT} NTT 了。

  不过在原根的性质里笔者提到 n n n 需满足 n ∣ ( p − 1 ) n |(p-1) n(p1),故能进行 模 p p p N T T \mathrm{NTT} NTT 的多项式长度会有一定限制,具体可以查阅开篇给定的数表。

// 歇会

你可能感兴趣的