Hensel 互素因子提升

已知 $g_n{h}_n$ 与 $f$ 的前 $n$ 位系数相同，下一步只改每个低次系数的第 $n$ 位：

乘积中 $p^{2n}uv$ 在模 $p^{n+1}$ 下消失。因此虽然原问题是乘法分解，下一位却由线性方程决定：

首一与次数条件使 $f-g_n{h}_n$ 的最高次项相消，所以 $\mathrm{deg}e<r+s$。待求的 $u,v$ 一共恰有 $r+s$ 个系数。互素性保证这次线性修正既能解出，又不会有第二种答案。

如何直接解出两组修正系数 ​

有限域多项式环的Euclidean 除余与Bézout回代理路欧几里得整环Euclidean domain带有允许带余除法并严格下降的欧几里得函数的整环。给出 $A,B$，满足

只需保存 $Amod\overline{g}$，以后每一层复用。令

第一个等式给 $\mathrm{deg}u<r$；因为 $A\overline{h}\equiv 1(\mathrm{mod}\overline{g})$，第二个分子确实被 $\overline{g}$ 整除。该分子的次数小于 $r+s$，所以商的次数小于 $s$，两项均符合要求。

若另有一组修正，取差得到 $\mathrm{\Delta }u\overline{h}+\mathrm{\Delta }v\overline{g}=0$。互素性推出 $\overline{g}\mid \mathrm{\Delta }u$，而 $\mathrm{deg}\mathrm{\Delta }u<r$，故 $\mathrm{\Delta }u=0$，随后 $\mathrm{\Delta }v=0$。这证明每层的唯一性；它来自完整的多项式系数恒等式，不是只在若干域元素上代入检查。

从系数的一位到完整因子 ​

将式(5)的系数选为 $0,\dots ,p-1$，代入修正式，乘积误差至少被 $p^{n+1}$ 整除，次数和首一性保持。起点取 $\overline{g},\overline{h}$ 的标准代表，归纳即得每一层。

任何另一对模 $p^{n+1}$ 因子降模后，按归纳假设必须等于 $g_n,h_n$；它们只能相差 $p^{n}u,p^{n}v$，而式(4)的解唯一。因此有限层唯一性已经包含所有可能系数，不依赖算法恰好选择了什么代表。

每个系数形成相容的 $p$ 进数字列，分别收敛到 ${\mathbb{Z}}_p$。次数固定，乘积每个系数只含有限个乘积，故极限满足 $f=gh$。若完整因子还有另一对，降到每一层均相同，所有系数差都被每个 $p^n$ 整除，只能为零。这样才得到式(2)的完整存在与唯一性。

把三进三次式分成二次块与一次块 ​

取

两块互素，即使 $X^2$ 自身有重因子也无妨。初始 $g_1=X^2,h_1=X+2$，有

模 $X^2$ 的逆元可取 $A=2+2X$，因为 $(2+2X)(X+2)=1+2X^2$ 于 ${\mathbb{F}}_3[X]$。式(5)给 $u=2,v=2$，故

下一步得到 $g_3=X^2+24,h_3=X+26$。再下一步的误差为 $e=2X^2+2X+2$，修正变成 $u=1+2X,v=0$，因此 $g_4=X^2+54X+51,h_4=X+26$。完整前六层为：

最后一行有逐系数证书

一次因子的根为 $-350\equiv 379(\mathrm{mod}729)$。二次因子上的 $375$、$378$ 分别是常数与一次项的系数，不能把其中某个数当成另一个近似根。

互素条件失败时，存在与唯一都可能失去 ​

$X^2-p$ 模 $p$ 分解成 $X\cdot X$，但它在 ${\mathbb{Q}}_p$ 中没有根：平方根会要求整数赋值等于 $1/2$。因此这两块无法提升成两个一次因子。

$X^2-p^2$ 同样降为 $X\cdot X$，却有 $(X-p)(X+p)$ 和交换次序后的两对有序提升。它们具有同样的两个剩余块，却不再唯一。假设失败并不自动说明无解，说明的是本页的存在唯一保证已经不适用。

此外，模 $p^N$ 的非零零因子不是域元素，不能在那里直接把每个非零多项式首项都取逆。算法中的逆元与除余在 ${\mathbb{F}}_p[X]$ 中进行；较高精度只用整系数加乘与已知整除的误差除以 $p^n$。

怎样证明例子已找全所有基域根 ​

把上述完整一次因子记为 $X-\rho$。系数比较给二次因子

由第二层的唯一因子已知 $\rho \equiv 1(\mathrm{mod}9)$，因此

二次因子的常数项赋值恰为1，首项赋值为0，一次项在连线之上。Newton多边形的单边分母判据理路Newton 多边形与根的赋值Newton polygon of a polynomial · 牛顿多边形 · Newton polygon valuation theorem由系数赋值构造下凸折线，证明乘积的斜率并集规律，并据此认证可能根赋值和不可约性。给出唯一斜率 $-1/2$，其分母等于次数2，故 $g$ 在 ${\mathbb{Q}}_3$ 上不可约。于是原三次式在整个 ${\mathbb{Q}}_3$ 中恰有一个根 $\rho$，并非只在某个有限余数表中找到一个。

这里的局部二次不可约性由有限精度已固定的赋值证书决定。无需先知道 $\rho$ 的所有数字，也无需把扩域中另两根写成根式。

与简单根和有限域分解如何衔接 ​

若指定块 $\overline{g}=X-\overline{a}$，另一个块与它互素等价于 ${\overline{f}}^{\prime }(\overline{a})\ne 0$。提升后 $g=X-\alpha$，因此简单根Hensel理路Hensel 引理：简单根的唯一提升Hensel's lemma · 亨泽尔引理模素数的简单根在指定余类内唯一提升为 p-adic 根，并以逐位递推计算 11-adic 的三的平方根。就是这个因子接口在一次块上的情形。对于模 $p$ 的重根，旧页的强Hensel条件可能仍能在更小的球中认证根；不能把它等同于式(1)的互素分块。

Berlekamp理路Berlekamp 多项式因式分解算法Berlekamp factorization algorithm · Berlekamp polynomial factorization计算有限域商代数的 Frobenius 不动子空间，并以 GCD 从中确定性分离不可约因子。或Cantor–Zassenhaus理路Cantor–Zassenhaus 因式分解算法Cantor–Zassenhaus algorithm · Cantor-Zassenhaus factorization先按不可约因子次数分组，再以随机幂、迹映射和 GCD 做 Las Vegas 等次数分裂。先在有限域中找因子。若 $\overline{f}$ 有重复因子，可将每个不可约因子的全部幂保持在同一块，再对不同块提升。各块之间仍互素；块内部可能需要进一步的局部方法，而不是把重复副本强行分开。

成本与验收 ​

设两个块均非常数，使用普通稠密乘除，预先求一次Bézout系数需 $O(d^2)$ 次有限域运算。逐位提升至 $p^N$ 有 $N-1$ 轮，每轮包含 $O(d^2)$ 次系数环运算与有限域乘除，所以可用保守预算 $O(N{d}^2)$；它不是位复杂度。工作系数有至多 $O(N\log p)$ 位，读取输入的成本及整数加乘成本必须另计。复用数组时，工作存储为 $O(d)$ 个模 $p^N$ 系数；若保存全部中间证书，还需另计其输出大小。

验收者可核初始互素Bézout等式、每层式(4)及次数约束、最终乘积同余。仅有最终乘积同余能证明输出合法，但唯一性仍依赖模 $p$ 的互素前提。二次块是否已不可约则另由式(7)的赋值证书认证，不能从“算法返回了两个块”自行推断。