多项式平方自由分解

形式陈述

设 $K$ 为完美域，输入是非零多项式 $f\in K[x]$ 。算法假定能够执行精确域运算；在正特征分支还提供系数的逆 Frobenius 运算。形式导数纯粹按幂次定义：

f(x)=\sum_{i=0}^{n}a_i x^i \quad\Longrightarrow\quad f'(x)=\sum_{i=1}^{n} i a_i x^{i-1},

其中整数 $i$ 映到 $K$ 的素子环；它不使用极限。平方自由分解要求写成

f=c\prod_{i\ge1}f_i^i,

其中 $c\in K^\times$ ，每个非恒等的 $f_i$ 首一、平方自由，且两两互素。输出只区分重数，不继续把 $f_i$ 分成不可约因子。

先取 $c=\operatorname{lc}(f)$ 并把工作多项式归一化为 $F=f/c$ ；若 $F=1$ ，返回单位 $c$ 与空的因子列表。下文所有 GCD 都取首一代表，所有因子除法都是精确除法。逐层剥离过程为

text

SquareFreeMonic(F):
    g = gcd(F, F'); w = F/g; i = 1; output = []
    while w != 1:
        y = gcd(w, g)
        z = w/y
        if z != 1: append (z, i) to output
        w = y; g = g/y; i = i+1
    if char(K) = p > 0 and g != 1:
        h = pth_root(g)
        for (z, j) in SquareFreeMonic(h): append (z, p*j)
    return output

底层GCD使用域上一元多项式的首一公因子；可由子结式 PRS实现，也可使用普通 Euclidean 除余。它是可替换的子程序。

为证明每个输出的重数，考察任一首一不可约因子 $q$ 在 $F$ 中的指数 $e$ 。完美性保证 $q'\ne0$ 。在特征零或 $p\nmid e$ 时， $q$ 在初始 $g$ 中的指数恰为 $e-1$ ，在 $w$ 中为一；第 $i$ 轮以前的状态依次剥去 $g$ 中的一层，因此恰在 $i=e$ 时， $q$ 进入 $z=w/y$ 。在 $p\mid e$ 时， $q^e$ 全留在 $g$ 中， $w$ 不含 $q$ ，此循环不会改动它。

所以循环结束后，特征零的 $g=1$ ；正特征的剩余 $g$ 只含指数被 $p$ 整除的不可约因子，满足 $g'=0$ 。形式导数为零等价于所有非零项次数都是 $p$ 的倍数。完美域的 Frobenius 映射 $a\mapsto a^p$ 为双射，故

g(x)=h(x)^p,\qquad h(x)=\sum_j a_{pj}^{1/p}x^j \quad\text{当 }g(x)=\sum_j a_{pj}x^{pj}.

递归把次数至少缩小为原来的 $1/p$ ，并将返回重数乘 $p$ 。这证明了终止、因子两两互素、各因子平方自由和复乘正确性；同一重数的因子可再相乘合并为一个 $f_i$ 。在有限域 $K=\mathbb F_{p^s}$ 中，逆 Frobenius 具体为 $a^{1/p}=a^{p^{s-1}}$ ，可由模域幂运算实现。

直觉

若 $f$ 含因子 $q^e$ ，则形式求导后至少还保留 $q^{e-1}$ ，在特征零中， $\gcd(f,f')$ 收集了重复部分，首一化后的商每种不可约因子只留下一个副本。随后连续取 GCD，就像一层层剥开等高线：第 $i$ 轮恰好分离原来重数为 $i$ 的因子。

正特征改变了这幅图像，因为 $p=0$ 在域中， $(h^p)'=ph^{p-1}h'=0$ 。导数对 Frobenius 像完全失明，不能从 $\gcd(f,f')=f$ 得出“算法失败后把整个 $f$ 当一个重数块”。正确动作是先识别纯 $p$ 次幂、在系数上取 Frobenius 逆并降低次数，然后递归恢复被 $p$ 放大的重数。

图示为特征零的剥离循环；进入循环前先将工作多项式首一化，原输入的首项系数 $c$ 单独返回。

例子与边界

在 $\mathbb Q[x]$ 中令

f=(x-1)^2(x+2)^3.

求导并提取公因子得到

f'=(x-1)(x+2)^2(5x+1),\qquad g=(x-1)(x+2)^2,

于是 $w=(x-1)(x+2)$ 。第一轮 $y=\gcd(w,g)=w$ ，没有重数 $1$ 的因子；更新后 $g=x+2$ 。第二轮得到 $y=x+2$ 、 $f_2=x-1$ ；第三轮得到 $f_3=x+2$ 。复乘 $f_2^2f_3^3$ 恢复原式，重数与因子都可直接核验。

在 $\mathbb F_2[x]$ 中，

x^4+x^2+1=(x^2+x+1)^2

的形式导数为零。若只运行特征零循环，会停在 $\gcd(f,0)=f$ 而没有进展；取平方根 $h=x^2+x+1$ 后可知唯一平方自由块的重数为 $2$ 。这不是数值导数精度问题，而是 Frobenius 的结构性边界。

完美性也不能藏掉。在不完美域 $\mathbb F_p(t)$ 上， $x^p-t$ 的导数为零，却没有系数仍在该域内的 $p$ 次根；“无平方因子”和“在代数闭包中无重根”的口径在此会分离。页面算法选择后者并以完美域为前提。常数、多项式零输入与非首一输入还需分别处理：零多项式没有唯一的有限重数分解，非零常数只贡献单位 $c$ 。

推论与应用

平方自由分解是完整因式分解的预处理。Berlekamp 算法和Cantor–Zassenhaus 算法通常都假设输入已经首一且平方自由；先去重后，随机分裂或 Frobenius 线性代数不用反复发现同一个不可约因子，也能用次数之和准确计量工作。

它还服务部分分式分解、符号积分、重根隔离与代数曲线奇异性检测。特征零中，首一化的 $f/\gcd(f,f')$ 是平方自由部分；正特征中要把完整分解得到的所有非恒等 $f_i$ 各乘一次。比如 $\mathbb F_2[x]$ 中上例的商为 $1$ ，实际平方自由部分却是 $x^2+x+1$ 。完整平方自由部分可避免后续算法重复处理同一个根；结式 $\operatorname{Res}(f,f')$ 是否为零则给出重根的快速判据。不过只知道判据为零不等于已经恢复各重数，完整输出仍需上述 GCD 链与正特征递归。

对次数 $n\ge1$ ，若使用普通稠密 Euclidean GCD 与精确除法，上述逐层剥离可取保守的 $O(n^3)$ 次域运算上界：同一层至多进行 $n$ 轮，每轮至多平方量级工作；正特征递归把次数至少除以 $p$ ，各层预算按几何级数求和。系数的逆 Frobenius 调用及其 bit 成本另计。复用稠密工作数组并按深度优先方式处理递归，可使用 $O(n)$ 个系数槽位，重数、递归控制信息与系数的实际 bit 存储分别计算。

参考资料

David Y. Y. Yun, “On Square-Free Decomposition Algorithms,” Proceedings of SYMSAC 1976, pp. 26–35.
Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013, chapters on polynomial GCD and finite-field factorization.
Keith O. Geddes, Stephen R. Czapor, and George Labahn, Algorithms for Computer Algebra, Kluwer, 1992, §8.2.
Karim Belabas, Advanced Computational Number Theory，2013-09-01，§3.1.3、Lemma 3.11：导数 GCD 只保留重数不被特征整除的因子，以及逆 Frobenius 的递归处理。

形式陈述 ​

反向链接

形式陈述