数论基础

有限域

在环的定义上多了每个元素一定存在乘法逆元,域的乘法运算是可交换的

有限域的阶是素数的整数次幂:$|G| = p^k$z.

证明:

假设有两个不同的素数p,q都整除|F|.考虑F的加法群,根据引理,存在a,b非零,但是pa=0,qb=0.而a,b可逆,因此pe=0,qe=0,其中e是F的乘法单位元.

而由p,q互素,存在整数A,B,满足Ap+Bq=1,则e=1*e=(Ap+Bq)*e=0.矛盾!

因此|F|只能有至多一个素因子,也就是F的阶一定是素数幂.

素域

阶为素数的域,加法,乘法由模阶数得到

扩展域

由素域扩展得到

如果有限域的阶不是素数,则这样的有限域内的加法和乘法运算就不能用模整数加法和整数乘法模p表示

如在扩展域$GF(2^m)$中,使用系数为$GF(2)$中元素的多项式表示,所以每个元素都能用一个以$a_n|a_n \in GF(2) = 0,1$表示,所以总数为$2^m$k.

按位计算$C(x)=A(x)+B(x) ,c_i=(a_i+b_i)\pmod 2$

按位计算$C(x) = A(x)*B(x) ,c_i为多项式相乘之后化简合并得到的系数$.

化简:

最后的结果模一个不可约多项式,无论何时,多项式系数都属于$a_n$.