Sinofine Lotusie

用于编码的有限域上多项式的分解

对 xn−1x^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 xi−1x^i-1
0 00
1 x+1x + 1
2 (x+1)2\left(x + 1\right)^{2}
3 (x+1)(x2+x+1)\left(x + 1\right) \left(x^{2} + x + 1\right)
4 (x+1)4\left(x + 1\right)^{4}
5 (x+1)(x4+x3+x2+x+1)\left(x + 1\right) \left(x^{4} + x^{3} + x^{2} + x + 1\right)
6 (x+1)2(x2+x+1)2\left(x + 1\right)^{2} \left(x^{2} + x + 1\right)^{2}
7 (x+1)(x3+x+1)(x3+x2+1)\left(x + 1\right) \left(x^{3} + x + 1\right) \left(x^{3} + x^{2} + 1\right)
8 (x+1)8\left(x + 1\right)^{8}
9 (x+1)(x2+x+1)(x6+x3+1)\left(x + 1\right) \left(x^{2} + x + 1\right) \left(x^{6} + x^{3} + 1\right)
10 (x+1)2(x4+x3+x2+x+1)2\left(x + 1\right)^{2} \left(x^{4} + x^{3} + x^{2} + x + 1\right)^{2}
11 (x+1)(x10+x9+x8+x7+x6+x5+x4+x3+x2+x+1)\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 (x+1)4(x2+x+1)4\left(x + 1\right)^{4} \left(x^{2} + x + 1\right)^{4}
13 (x+1)(x12+x11+x10+x9+x8+x7+x6+x5+x4+x3+x2+x+1)\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 (x+1)2(x3+x+1)2(x3+x2+1)2\left(x + 1\right)^{2} \left(x^{3} + x + 1\right)^{2} \left(x^{3} + x^{2} + 1\right)^{2}
15 (x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1)\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)

方法如下:

  1. 首先考虑 nn 是否含有有限域特征的幂, 若 n=mqkn=mq^k , 则将其首先分解为 xn−1=(xm−1)qkx^n-1=(x^m-1)^{q^{k}} ;

  2. 其次考虑 m+1m+1 是否是有限域特征的幂, 考虑如下定理,

设 qq 是有限域 FqF_q 的特征, 则有限域上的多项式 xqn−xx^{q^n}-x 有分解

xqn−x=∏d|nϕd(x), x^{q^n}-x=\prod_{d|n}\phi_d(x),
其中 ϕd(x)\phi_d(x) 是阶为 dd 的首一不可约多项式乘积.

故可分解. 如

x15−1=1x(x16−x)=1x∏d=1,2,4ϕd(x)=1xx(x+1)(x2+x+1)(x4+x3+1)(x4+x+1)(x4+x3+x2+x+1)=(x+1)(x2+x+1)(x4+x3+1)(x4+x+1)(x4+x3+x2+x+1)\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=FpnF=F_{p^n} ,设 α\alpha 是 FF 的生成元(举例, 设 Fpn=F[x]/(f(x))F_{p^n} = F[x]/(f(x)) , α\alpha 是 f(x)f(x) 的根), 有群 G=(αp)(modpn−1)⊂FG=(\alpha^p) \pmod{p^n-1}\subset F , 可以得到轨道 aG,a∈FaG, a\in F . 可以证明以下结论:

以某轨道的所有元素为唯一单根的多项式是 FpF_p 上的极小多项式.

该轨道也称 Cyclotomic Coset, 至于为什么叫 coset 我不大能理解.

我们发现由orbitmini, 轨道正好(同构意义下)把域的元素划分为了不同等价类, 并且每个等价类都对应某个不可约多项式, 将这些不可约多项式乘起来即印证(不是证明)了uniqfact 中的分裂域描述.