有限域上多项式因子分解的 Cantor–Zassenhaus 过程以及 Kedlaya

首先让我们明确计算时间的记号. 我们接下来用 \(\tilde O(\bullet)\) 表示忽略 \(\log n\) 和 \(\log \log q\) 的因子. 因为在计算机代数中考虑的有限域 \(\mathbb F_q\) 有可能 \(q\) 是非常大的数, 所以计算的过程关于 \(\log q\) 的次数也是需要考虑的.

之所以本文说的是 "Cantor–Zassenhaus 过程" 而非 "算法", 其实是一家之言, 这里是想体现, 这个过程中已经使用了相当多的已知的重要算法, 例如读者应该至少接受如下事实:

\(\mathbb F_q\) 上的基本算术运算 (加减乘除) 可以在 \(\tilde O(\log q)\) 时间内完成.
\(\mathbb F_q\) 上的 \(n\) 次多项式的乘法, 还有 Euclid 算法, 可以在 \(\tilde O(n \log q)\) 时间内完成.

再比如, 读者应当知晓一些关于有限域的基本知识:

大小为 \(q\) 的有限域 \(\mathbb F_q\) 一定形如 \(q = p^k\), 进一步地, \(\mathbb F_q\) 可以视作基域的代数闭包 \(\overline{\mathbb F_p}\) 中 \(X^q - X\) 的解, 或者 \(\mathbb F_p\) 关于 \(X^q-X\) 的分裂域.
\(X^{q^k} - X\) 是所有 \(\mathbb F_q\) 上次数为 \(k\) 的约数的不可约多项式的乘积.
在实际的计算意义上, 实现方式是选取一个 \(k\) 阶不可约多项式 \(f(T)\), 然后将 \(\mathbb F_q\) 识别为 \(\mathbb F_p [T] / f(T)\).

热身: 有限域上求根

给定一个 \(n\) 次 \(\mathbb F_q\) 上多项式, 求它在 \(\mathbb F_q\) 上在那些位置为零.

第一步是清理. 首先注意到, \(X^q - X = \prod_{\alpha\in \mathbb F_q} (X - \alpha)\), 如果取 \(\gcd(f(X), X^q-X)\), 就将多项式的所有根保留刚好一次.

这个 \(\gcd\) 的计算过程的瓶颈是计算 \(X^q \bmod f\), 这需要 \(\log q\) 次迭代, 所以时间是 \(\tilde O(n\log^2 q)\).

第二步是分裂. 现在不妨设剩下的多项式次数是 \(n\), 我们已经知道它一定有 \(n\) 个不同的根了. 那么我们知道, 根据中国余数定理,

\[\mathbb F_q[X]/f(X) \cong \prod_{f(\alpha) = 0} \mathbb F_q. \]

现在考虑在剩余系 \(F_q[X]/f(X)\) 中均匀随机 (这就是直接随机一个 \(n-1\) 次多项式), 对应的在同构侧也就相当于是均匀随机的.

让我们先解决 \(q\) 是奇数的情况, 这个情况下, 我们考虑这个随机的多项式 \(r(X)\), 取它的 \((q-1)/2\) 次幂, 就得到了

\[r(X)^{(q-1)/2} \iff ( r(\alpha)^{(q-1)/2} )_{\alpha}, \]

也就是说, 每个分量都被取了 \((q-1)/2\) 次幂, 此时 \(0\) 被映到 \(0\), 其他数以相等的概率映到 \(\pm 1\). 所以, \(r(X)^{(q-1)/2} - 1\) 根据同构映到的每个分量, 有 \((q-1)/2\) 的概率是 \(0\), 剩下的概率非零.

这样就说明, 我们如果取 \(\gcd(r(X)^{(q-1)/2} - 1, f(X))\), 每个根就有大概 \(1/2\) 的独立概率落在 \(\gcd\) 里, 剩下的概率不在, 我们就可以通过这个手段将 \(f(X)\) 的根均匀分成两半了.

时间复杂度还是 \(\tilde O(n\log^2 q)\).

综上, 这个算法的时间复杂度是 \(\tilde O(n\log^2 q)\).

对于特征为 \(2\) 情况的补全

令 \(q = 2^k\), 考虑 Frobenius 自同构 \(\phi_2\colon x\mapsto x^2\), 令

\[ \varphi = \sum_{i = 0}^{k-1} \phi_2^{2^i} \colon x \mapsto x + x^2 + \cdots + x^{2^{k-1}}. \]

注意到在 \(\mathbb F_q\) 上有 \(\phi_q = 1\), 所以 \(\varphi(x)^2 = \varphi(x)\), 说明 \(\varphi(x) \in \mathbb F_2\), 而且 \(\varphi\) 作为多项式的次数是 \(2^{k-1}\), 这说明它一定把 \(\mathbb F_q\) 上一半的元素映到了 \(0\), 另一半映到了 \(1\).

所以只需要求 \(\gcd(\varphi(r(X)), f(X))\) 就可以实现类似的分裂过程, 时间复杂度也是 \(\tilde O(n\log^2 q)\).

因子分解过程

主流的多项式因子分解过程在大方向上分三个阶段.

不同次因子分解. 这部分是对于每个 \(i\), 把 \(f\) 包含的 \(i\) 次不可约多项式提取出来.
同次因子分解. 这部分是已知 \(g\) 是一些互异的 \(i\) 次不可约多项式之乘积, 然后具体找出这些不可约多项式.
无平方因子分解. 这部分是将 \(i\) 次的部分分解完成后, 求出原多项式中这些不可约因子的重数.

同次因子分解 (Cantor–Zassenhaus)

我们故技重施, 已知多项式 \(f(X)\) 分解成了不可约的互异 \(i\) 次因子之乘积, 那么中国余数定理给出

\[\mathbb F_q[X] / f(X) \cong \prod_{g(X) \mid f(X)}(\mathbb F_{q}[X] / g(X)), \]

进而有 \(\mathbb F_{q}[X] / g(X) \cong \mathbb F_{q^i}\).

所以 \(q\) 是奇数的时候, 我们还是随机一个多项式, 取 \((q^i-1)/2\) 次幂做类似的事情. \(q\) 是偶数的时候, 就用特征为 \(2\) 的时候的相应手段, 就可以分裂这个多项式.

时间复杂度 \(\tilde O(ni \log^2 q)\).

完整过程

首先枚举 \(i\) 从 \(1\) 到 \(n\), 维护一个 \(r_i\) 表示 \(X^{q^i} \bmod f(X)\), 初始化 \(r_0 = 1\).

计算 \(r_i = r_{i-1}^q \bmod f\).
计算 \(\gcd(r_i - X, f(X))\), 然后通过 Cantor–Zassenhaus 过程分解出这部分的各不可约因子.
利用每个因子试除 \(f\), 把这些因子都除掉.

这个过程的正确性是这么保证的: 在第 \(i\) 轮结束后, 我们已经清理了 \(f\) 中所有次数 \(\leq i\) 的不可约多项式, 那么对下一轮而言, \(X^{q^{i+1}}-X\) 和 \(f(X)\) 的公因式, 就只可能是 \(i+1\) 次的了.

时间复杂度是 \(\tilde O(n^2 \log^2 q)\) 的, 一部分瓶颈来自第 1 步, 以及第 2 步传进去的多项式次数之和是 \(n\). 第 3 步总共试除只会发生不超过 \(2n\) 次.

更快的改进 (Kedlaya–Umans)

我们已经在另一篇博客里提到了 Kedlaya–Umans 的工作: 有限域上的多项式复合 \(f(g)\bmod h\) 可以在 \(n^{1+o(1)}\) 次运算中完成, 经过分析, 他们的做法加上 \(\log q\) 的依赖的话, 复杂度是

\[n^{1+o(1)}\log^{1+o(1)}q. \]

通过这个有力的武器, 我们可以进一步优化 Cantor–Zassenhaus 过程.

更快的 Cantor–Zassenhaus

首先考虑如何优化同次因子分解. 现在已知不可约多项式的次数为 \(i\).

对于 \(q\) 是奇数的情况, 需要优化 \(r(X)^{(q^i-1)/2} \bmod f\) 的计算. 首先, 注意到

\[\frac{q^i-1}2 = \frac{q-1}{2} \cdot \frac{q^i-1}{q-1} = \frac{q-1}{2} \cdot (1 + q + \cdots + q^{i-1}), \]

我们首先需要算出 \(s(X) = r(X)^{(q-1)/2} \bmod f\), 然后计算

\[ \begin{align*} &\quad s(X)s(X)^q \cdots s(X)^{q^{i-1}} \bmod f\\ &= s(X)s(X^q) \cdots s(X^{q^{i-1}}) \bmod f. \end{align*} \]

这样就很健康了, 我们其实只需要知道怎么快速计算 \(s(X^{q^i})\), 就可以类似维护快速幂的方式算它了. 这其实就是设 \(h_i(X) = X^{q^i} \bmod f\), 那么我们有

\[X^{q^{i+j}} = X^{q^i} \circ X^{q^j} \equiv X^{q^i} \circ h_j = h_j(X^{q^i}) \equiv h_j \circ h_i, \]

所以 \(X^{q^i}\) 是可以 (调用复合的) 快速幂计算的. 注意对一般的多项式复合来说, \(f(g)\bmod h\) 是不能把 \(f\) 取模的!

我们就把代价从 \(\tilde O(ni\log^2 q)\) 降低到了 \(n^{1+o(1)} \log^{2+o(1)}q\). 更仔细地分析的话, 注意到当我们用 \(\tilde O(n\log^2 q)\) 处理好 \(X^q \bmod f(X)\) 之后, 之后的操作就是 \(n^{1+o(1)} \log^{1+o(1)}q\) 的了.

对于如何优化特征为 \(2\) 的情况, 这个时候我们要快速计算

\[r(X) + r(X)^2 + r(X)^4 + \cdots + r(X)^{q^i/2} \bmod f, \]

方法也是类似的, 留作习题.

更快的不同次因子分解 (Kaltofen–Shoup)

我们之前暴力枚举了 \(i\) 从 \(1\) 到 \(n\), 这产生了起手 \(n^2\) 的严重代价, 但注意到一个整数拆分里出现的不同的整数顶多 \(O(n^{1/2})\) 种, 我们是有可能压低复杂度的, 如果能略过那些不需要的部分的话. 如果我们已知了出现的不可约因式的次数是 \(d_1,\dots,d_k\) 的话, 只需要 \(kn^{1+o(1)}\log^{1+o(1)} q + \tilde O(n\log^2 q)\) 的时间就能完成不同次因子分解了.

那么如何做到呢? 首先考虑给定 \(f\), 我们如果想要分解出 \(1\sim d\) 次的部分的话, 未必要刚好分离出一次, 而是先能分就分出来, 因为我们最后总能定位到唯一的位置, 然后精确计算 \(\gcd(X^{q^d}-X,f)\) 的.

考虑 \(b=\lfloor \sqrt d\rfloor\), 设多项式

\[P(Z) = \prod_{i=0}^{b-1} (Z - X^{q^i}), \]

那么就有

\[P(X^{q^{jb}}) = \prod_i (X^{q^{jb}} - X^{q^i})= \prod_i (X^{q^{jb-i}} - X)^{q^i}. \]

所以, 如果我们能求出

\[Q(X) = \prod_{j=0}^{b-1} P(X^{q^{jb}}), \]

那么 \(Q(X)\) 就包含了所有次数 \(\leq b^2\) 的不可约多项式, 再补上剩下的 \(O(\sqrt d)\) 项就可以了. 事实上, 把 \(P\) 看做 \(\mathbb F_q[X]/f(X)\) 上的一个多项式, 首先它可以在 \((n \sqrt d \log q)^{1+o(1)}\) 时间内求出, 其次, Kedlaya–Umans 的多点求值算法实际上也是可以处理这个情况的, 复杂度还是 \((n \sqrt d \log q)^{1+o(1)}\). 所以我们只需要对 \(P\) 多点求值, 然后计算乘积就真的完成了这部分工作.

然后我们对 \(Q(X)\) 乘以剩下的项得到 \(Q_0(X)\), 那么 \(\gcd(Q_0(X)^n, f(X))\) 就分离出了 \(f\) 的次数 \(\leq d\) 的部分.

这样我们就可以对输入的多项式分治, 分治的形式类似于

\[T(m) = 2T(m/2) + (m\sqrt n \log q)^{1+o(1)}, \]

所以最后复杂度是 \(n^{1.5+o(1)}\log^{1+o(1)}q\).

更快的无平方因子分解

现在我们其实已经把问题转换成了如下情况: 知道 \(f\) 分解成一些 \(d\) 次不可约多项式, 并且已经找出来他们是 \(g_1\cdots g_r\), 求他们的重数.

现在设 \(f = \prod g_i^{a_i}\), 那么 \(f'/f = \sum a_i g_i'/g_i\), 所以我们把 \(f'/f\) 约分得到 \(u/v\), 然后对 \(u\) 分治取模每个 \(g_i\), 得到了 \(u \bmod g_i = a_i g_i'\) 的 \(a_i\) 就是重数...

吗? 这个值是 \(\bmod p\) 的. 当我们把 \(\bmod p\) 部分的重数计算出来之后, \(f / \prod g_i^{a_i\bmod p} = f_1\) 是每个不可约因子的次数都是 \(p\) 的倍数, 这说明

\[f_1 = \prod_i g_i(x)^{b_i p}= \prod_i \phi_p[g_i](x^p)^{b_i}, \]

所以我们需要对 \(f_1(x^{1/p})\) 对每个 \(\phi_p[g_i]\) 计算重数. 这个递归会让次数除以至少 \(2\), 所以子问题的时间不是大头.

这部分的复杂度也被 \(\tilde O(n\log^2 q)\) 控制.

总结

综上, 经过优化之后, 我们多项式因子分解的复杂度就从 \(\tilde O(n^2 \log^2 q)\) 优化到了 \(n^{1.5+o(1)}\log^{1+o(1)}q + n^{1+o(1)} \log^{2+o(1)}q\), 这个思路大概是目前关于 \((n, \log q)\) 两个参数 Pareto 最优的做法.