对 \(x^n-1 \)的多项式分解的一些技巧.
from sympy import GF,symbols,factor,latex
x=symbols('x')
F = GF(2)
l = [['i',r'\(x^i-1\)'],None]
for i in range(16):
l.append([i,r"\("+latex(factor(x**i-1,domain=F))+"\)"])
return l| i | \(x^i-1\) |
|---|---|
| 0 | \(0\) |
| 1 | \(x + 1\) |
| 2 | \(\left(x + 1\right)^{2}\) |
| 3 | \(\left(x + 1\right) \left(x^{2} + x + 1\right)\) |
| 4 | \(\left(x + 1\right)^{4}\) |
| 5 | \(\left(x + 1\right) \left(x^{4} + x^{3} + x^{2} + x + 1\right)\) |
| 6 | \(\left(x + 1\right)^{2} \left(x^{2} + x + 1\right)^{2}\) |
| 7 | \(\left(x + 1\right) \left(x^{3} + x + 1\right) \left(x^{3} + x^{2} + 1\right)\) |
| 8 | \(\left(x + 1\right)^{8}\) |
| 9 | \(\left(x + 1\right) \left(x^{2} + x + 1\right) \left(x^{6} + x^{3} + 1\right)\) |
| 10 | \(\left(x + 1\right)^{2} \left(x^{4} + x^{3} + x^{2} + x + 1\right)^{2}\) |
| 11 | \(\left(x + 1\right) \left(x^{10} + x^{9} + x^{8} + x^{7} + x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1\right)\) |
| 12 | \(\left(x + 1\right)^{4} \left(x^{2} + x + 1\right)^{4}\) |
| 13 | \(\left(x + 1\right) \left(x^{12} + x^{11} + x^{10} + x^{9} + x^{8} + x^{7} + x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1\right)\) |
| 14 | \(\left(x + 1\right)^{2} \left(x^{3} + x + 1\right)^{2} \left(x^{3} + x^{2} + 1\right)^{2}\) |
| 15 | \(\left(x + 1\right) \left(x^{2} + x + 1\right) \left(x^{4} + x + 1\right) \left(x^{4} + x^{3} + 1\right) \left(x^{4} + x^{3} + x^{2} + x + 1\right)\) |
方法如下:
首先考虑 \(n \)是否含有有限域特征的幂, 若 \(n=mq^k \), 则将其首先分解为 \(x^n-1=(x^m-1)^{q^{k}} \);
其次考虑 \(m+1 \)是否是有限域特征的幂, 考虑如下定理,
设 \(q \) 是有限域 \(F_q \)的特征, 则有限域上的多项式 \(x^{q^n}-x \)有分解 \[ x^{q^n}-x=\prod_{d|n}\phi_d(x), \] 其中 \(\phi_d(x) \)是阶为 \(d \)的首一不可约多项式乘积.
故可分解. 如
\[\begin{align*}
x^{15}-1&=\frac{1}{x}(x^{16}-x)\\
&=\frac{1}{x}\prod_{d=1,2,4}\phi_d(x)\\
&=\frac{1}{x}x(x+1)(x^2+x+1)(x^4+x^3+1)(x^4+x+1)(x^4+x^3+x^2+x+1)\\
&=(x+1)(x^2+x+1)(x^4+x^3+1)(x^4+x+1)(x^4+x^3+x^2+x+1)
\end{align*}
\]
有限域上的极小多项式
考虑有限域 \(F=F_{p^n} \),设 \(\alpha \)是 \(F \)的生成元(举例, 设 \(F_{p^n} = F[x]/(f(x)) \), \(\alpha \)是 \(f(x) \)的根), 有群 \(G=(\alpha^p) \pmod{p^n-1}\subset F \), 可以得到轨道 \(aG, a\in F \). 可以证明以下结论:
以某轨道的所有元素为唯一单根的多项式是 \(F_p \)上的极小多项式.
该轨道也称 Cyclotomic Coset, 至于为什么叫 coset 我不大能理解.
我们发现由orbitmini, 轨道正好(同构意义下)把域的元素划分为了不同等价类, 并且每个等价类都对应某个不可约多项式, 将这些不可约多项式乘起来即印证(不是证明)了uniqfact 中的分裂域描述.