因子搜索台 · 04 B
没有根，还能拆开吗？
四次多项式可能拆成两个二次因子。检查所有域元素之后，我们继续用低次首一多项式试除，看看余式是否真的都非零。
首项系数固定为 1。修改其余整数系数后按模 p 化简；每次改动都会重新开始因子搜索。
把域里的每个元素代进去
用低次首一因子逐一试除
点选一个候选，看余式
为什么搜索到这里就够了
若 n 次多项式能写成两个正次数因子的乘积，两个因子的次数相加为 n，其中至少一个不超过 ⌊n/2⌋。在域上，非零首项系数可逆，可以把这个因子化成首一形式。
这套有限搜索只适用于这里的有限域与有限次数。“没有一次根”与“排除了全部可能的因子”是两件事。重复出现的因子也算非平凡分解。