用于编码的有限域上多项式的分解
October 30, 2022
对
x n − 1 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
0
0 0
1
x + 1 x + 1
2
( x + 1 ) 2 \left(x + 1\right)^{2}
3
( x + 1 ) ( x 2 + x + 1 ) \left(x + 1\right) \left(x^{2} + x + 1\right)
4
( x + 1 ) 4 \left(x + 1\right)^{4}
5
( x + 1 ) ( x 4 + x 3 + x 2 + x + 1 ) \left(x + 1\right) \left(x^{4} + x^{3} + x^{2} + x + 1\right)
6
( x + 1 ) 2 ( x 2 + x + 1 ) 2 \left(x + 1\right)^{2} \left(x^{2} + x + 1\right)^{2}
7
( x + 1 ) ( x 3 + x + 1 ) ( x 3 + x 2 + 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 ) ( x 2 + x + 1 ) ( x 6 + x 3 + 1 ) \left(x + 1\right) \left(x^{2} + x + 1\right) \left(x^{6} + x^{3} + 1\right)
10
( x + 1 ) 2 ( x 4 + x 3 + x 2 + x + 1 ) 2 \left(x + 1\right)^{2} \left(x^{4} + x^{3} + x^{2} + x + 1\right)^{2}
11
( x + 1 ) ( x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + 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 ( x 2 + x + 1 ) 4 \left(x + 1\right)^{4} \left(x^{2} + x + 1\right)^{4}
13
( x + 1 ) ( x 12 + x 11 + x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + 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 ( x 3 + x + 1 ) 2 ( x 3 + x 2 + 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 ) ( x 2 + x + 1 ) ( x 4 + x + 1 ) ( x 4 + x 3 + 1 ) ( x 4 + x 3 + x 2 + 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)
方法如下:
首先考虑
n n 是否含有有限域特征的幂,
若
n = m q k n=mq^k ,
则将其首先分解为
x n − 1 = ( x m − 1 ) q k x^n-1=(x^m-1)^{q^{k}} ;
其次考虑
m + 1 m+1 是否是有限域特征的幂,
考虑如下定理,
设
q q
是有限域
F q F_q 的特征,
则有限域上的多项式
x q n − x x^{q^n}-x 有分解
x q n − x = ∏ d | n ϕ d ( x ) , x^{q^n}-x=\prod_{d|n}\phi_d(x),
其中
ϕ d ( x ) \phi_d(x) 是阶为
d d 的首一不可约多项式乘积.
故可分解. 如
x 15 − 1 = 1 x ( x 16 − x ) = 1 x ∏ d = 1 , 2 , 4 ϕ d ( x ) = 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 ) \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 F=F_{p^n} ,设
α \alpha 是
F F 的生成元(举例,
设
F p n = F [ x ] / ( f ( x ) ) F_{p^n} = F[x]/(f(x)) ,
α \alpha 是
f ( x ) f(x) 的根),
有群
G = ( α p ) ( mod p n − 1 ) ⊂ F G=(\alpha^p) \pmod{p^n-1}\subset F ,
可以得到轨道
a G , a ∈ F aG, a\in F .
可以证明以下结论:
以某轨道的所有元素为唯一单根的多项式是
F p F_p
上的极小多项式.
该轨道也称 Cyclotomic Coset, 至于为什么叫 coset 我不大能理解.
我们发现由orbitmini,
轨道正好(同构意义下)把域的元素划分为了不同等价类,
并且每个等价类都对应某个不可约多项式,
将这些不可约多项式乘起来即印证(不是证明)了uniqfact 中的分裂域描述.