x^7+1=(x^4+x^2+x+1)(x^3+x+1) 是如何分解得到的呢？ 第1页

零、这题在问啥

CRC 校验码与题主的问题其实没有什么关系，题主只是在处理 CRC 校验码时遇到了这样一个因式分解，而疑问在于这样的因式分解是如何做到的。也就是说，题主关心的问题应该是：

如何在有限域 上对 (或其他多项式)进行因式分解？

下面的回答也仅仅针对这个问题，与 CRC 校验码无关。

一、问题的归约

对于 上形如 的多项式，我们有如下定理：

定理1. ,其中 是 上所有的 次首一不可约多项式之积。

就是说这样的多项式，恰好是次数整除 的所有首一不可约多项式的乘积。具体到题主的问题：因为

所以

.

注：因为在 中加法和减法是一样的，因此直接做了替换。 上的一次不可约多项式有 和 ,三次的有 和 。由于次数较小，可以通过简单的试除得到该结论。

而对于一般的 型多项式。我们假设多项式的根 被添加进了有限域，那么自然地， 也都是它的根，这些根构成了一个循环群。另外，因为这个多项式只有 个根，我们有

.

现在讨论较小的域。注意到 的阶 ,而对 的每个因子 ，有 个 以 为阶。那么我们有

其中

是分圆多项式。这样，我们就把 型的多项式分解问题转化成了分圆多项式 的问题。

二、分圆多项式

简单起见，这里不加证明地直接给出定理。

定理2.设 则在域 上 可以分解为 个 次不可约多项式之积。其中 是满足 的最小正整数。

我们拿题主的式子为例。对于 ，它应该等于 。其中 比较显然。我们来看看 ：由于 ，而 ,因此它可以分解为 个 次不可约多项式的乘积。这和我们的结论一致。

再比如对于 。由于 ，而 ，因此它可以分解为 个 次不可约多项式，也就是说它本身就是一个四次不可约多项式。

而对于 。由于 , ,因此它可以分解为 个 次不可约多项式的乘积。具体的求解可以通过待定系数法，这里不再赘述。

当然，待定系数法还是比较麻烦的，所以我们可以利用一个专门针对此问题的算法：Berlekamp 算法。

三、Berlekamp 算法

设 是 上 次首一多项式，若 满足

则有

当然上式有可能没有用，因为分解出来的式子可能是平凡的。但只要原式可以分解，就一定可以找到这样的 使得上式可以分解出非平凡因子。这样，算法的主要问题就变成了找到合适的 ，对此问题有如下定理：

定理3. 上的多项式满足上述要求的充要条件为： 对所有的 成立。

由于 是一个置换，因此其中可能会有循环，而每个循环都对应一个多项式。这些多项式都满足上述条件，可以进行分解。

四、总结

对于形如 或 的多项式，可以化为分圆多项式的乘积。分圆多项式的分解则先利用定理2确定其分解结果的形式，再通过待定系数法或 Berlekamp 算法求解。在使用后者时，可以通过定理3更好地选择 ，加快分解。

总地来说，有限域上任意多项式的分解并没有一个很好的算法去解决，而本文中的情形属于常用情形。