Berlekamp 多项式因式分解算法

Berlekamp 算法没有逐个试除不可约多项式，而是寻找在 Frobenius 下不动的“标签函数”。在每个不可约因子对应的扩域分量中，满足 $z^q=z$ 的元素恰是基域 ${\mathbb{F}}_q$；所以一个不动元素相当于给每个未知因子贴上一个域元素标签。计算 $gcd(f,h-a)$ 就把标签为 $a$ 的分量一次取出。

关键工作由有限维线性代数完成。模 $f$ 把任意幂压回 $n$ 维空间，Frobenius 的不动条件变成齐次线性方程；零空间维数不仅指导分裂，还直接告诉算法共有多少个互异不可约因子。这种结构尤其适合 $q$ 固定而 $n$ 增长的场景，因为所有域元素都可枚举，确定性地尝试 $a$ 不会改变关于 $n$ 的多项式性。

在 ${\mathbb{F}}_2[x]$ 中取

$f^{\prime }=x^2$，与 $f$ 互素，所以输入平方自由。以 $(1,x,x^2)$ 为基，平方映射给出

因此

$\ker (Q-I)$ 由 $1$ 与 $h=x+x^2$ 张成，维数 $2$ 预告两个因子。实际计算

商即 $x^2+x+1$。每个输出都通过精确除法验证，零空间本身没有“猜中因子”的概率。

复杂度声明必须保留 $q$。经典确定性版本需枚举 $a\in {\mathbb{F}}_q$ 并做稠密 $n\times n$ 线性代数；在固定 $q$ 时它关于 $n$ 为多项式时间，按本页逐基向量、逐常数细化的直接实现，可给出保守上界 $O(n^2\log q+q{n}^3)$ 次域运算，但 $q$ 若以 $\log q$ bit 输入，这个枚举对输入长度是指数依赖。不能把“有限域上的多项式时间”省略成对 $n,\log q$ 都多项式。

具体地，先以重复平方求 $z=x^{q}modf$，朴素成本 $O(n^2\log q)$；再依次乘 $z$ 得到各列，共 $O(n^3)$。行化简也是 $O(n^3)$。至多 $n$ 个基向量各枚举 $q$ 个常数，每次对当前因子做普通除余和 GCD；这些因子的次数和至多 $n$，一次细化的保守预算为 $O(n^2)$，给出上述界。扩域的表示和每次域运算的 bit 成本仍须另计。大 $n$ 时矩阵可稀疏开始却在消元中变稠密；非首一输入需先除首项，首项为零或底环不是域时则没有这一操作。零空间维数为 $1$ 只在输入已平方自由的前提下才证明 $f$ 不可约。

Berlekamp 不动子空间给出了一个很强的可检验证书：零空间基、各次 GCD 与最终乘积足以复核分解。算法还展示 Frobenius、Chinese remainder 与线性代数如何协作，把非线性的“找因子”问题转成求核再分组。编码理论和有限域构造中的小特征多项式因此常直接采用此路线。

Cantor–Zassenhaus 算法理路Cantor–Zassenhaus 因式分解算法Cantor–Zassenhaus algorithm · Cantor-Zassenhaus factorization先按不可约因子次数分组，再以随机幂、迹映射和 GCD 做 Las Vegas 等次数分裂。通常先按不可约因子次数分组，再用随机幂与 GCD 做等次数分裂；它是 Las Vegas 算法，避免经典 Berlekamp 对全部 $q$ 个常数的确定性扫描，在大域上更合适。两者不是“一个永远更快”：小固定域、需要完全确定性或已有高效线性代数时，Berlekamp 仍然自然；大 $q$ 和高次数时，随机分裂及其现代变体往往占优。比较时应同时报告域大小编码、矩阵算法与随机性口径。

稠密矩阵及其零空间基合计需要 $O(n^2)$ 个域元素槽位；域元素的具体表示位数另计。

若输入来自一个首一整数多项式的模 $p$ 约化，这里的因子表还可作为p-adic互素因子提升理路Hensel 互素因子提升Hensel factor lifting · Coprime polynomial Hensel lifting · 亨泽尔因子提升从互素首一模素数因子出发，逐位求解唯一系数修正，构造完整p-adic因子并交付有限精度乘积证书。的起点。先把相同不可约因子的全部重数放在同一块，保证不同块彼此互素，再提升其系数；单块内部不必平方自由。提升在 ${\mathbb{Z}}_p[X]$ 中输出因子，不会自动证明这些因子具有有理数系数，也不能在含零因子的 $\mathbb{Z}/p^N\mathbb{Z}$ 上原样调用本页的有限域矩阵算法。