伽罗华域（有限域）及其运算规则（包含大量例子）

大家好，欢迎来到IT知识分享网。

模运算

除法定理
Z = { ⋯   , − 1 , 0 , 1 , ⋯   } \mathbb{Z}=\{\cdots,-1,0,1,\cdots\} Z={
⋯,−1,0,1,⋯}为整数集，对任何整数a和任何正整数n存在唯一整数q和r，满足 { r : 0 ≤ r < n , r ∈ Z } \{r:0\le r<n,r\in \mathbb{Z}\} {
r:0≤r<n,r∈Z},且$a=qn+r$。称$q=\lfloor a/n\rfloor$为除法的商，$\lfloor \rfloor$表示向下取整， $r\equiv a\mathrm{mod}n$为除法的余数。
简单例子
$19\mathrm{mod}11\equiv 8\mathrm{mod}11$
$-7\mathrm{mod}11\equiv 4\mathrm{mod}11$
模运算的好处：一些程序进行线性运算的时候，由于存储空间大小是固定的，可能存在结果溢出的情况，模运算可以将$x$结果始终确定在一个范围即 { x : 0 ≤ x < n , x ∈ Z } \{x:0\le x<n,x\in \mathbb{Z}\} {
x:0≤x<n,x∈Z}内，从而避免溢出。

有限群

群$(S,\oplus )$是集合$S$和二元运算符$\oplus$组成，顾名思义群中的元素个数是有限的。对于该运算应该满足以下性质：

• 封闭性：对于任意$a,b\in S$，有$a\oplus b\in S$。
• 单位元：存在一个元素$e\in S$，称$e$为单位元，对所有$a\in S$，满足$e\oplus a=a\oplus e=a$。
• 结合律：对任意$a,b,c\in S$,有$(a\oplus b)\oplus c=a\oplus (b\oplus c)$。
• 逆元：对任意$a\in S$，存在$b\in S$，满足$a\oplus b=b\oplus a=e$。

模n加法群

定义群$({\mathbb{Z}}_n,{+}_n)$，其中 Z n = { x ∣ 0 ≤ x < n , x ∈ Z } \mathbb{Z}_n=\{x|0\le x<n,x\in\mathbb{Z}\} Zn​={
x∣0≤x<n,x∈Z}，${+}_n$指在模n上的加法，即$a{+}_{n}b=a+b\mathrm{mod}n$，群$({\mathbb{Z}}_5,{+}_5)$的运算表为

在该群中单位元为0，0的逆元为0，1的逆元为4。

模n乘法群

定义群$({\mathbb{Z}}_n^{\ast },{\cdot }_n)$,其中 Z n ∗ = { x ∈ Z n ∣ g c d ( a , n ) = 1 } \mathbb{Z}^*_n=\{x\in \mathbb{Z}_n|gcd(a,n)=1\} Zn∗​={
x∈Zn​∣gcd(a,n)=1}，$gcd(a,n)$表示求a和n的最大公因数，若两数的最大公因数为1则两个数互素，${\cdot }_n$指在模n上的乘法，即$a{\cdot }_{n}b=a\cdot b\mathrm{mod}n$，群$({\mathbb{Z}}_8^{\ast },{\cdot }_8)$的运算表为

注意 Z 8 ∗ = { 1 , 3 , 5 , 7 } ≠ { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } \mathbb{Z}_8^*=\{1,3,5,7\}\ne\{0,1,2,3,4,5,6,7\} Z8∗​={
1,3,5,7}={
0,1,2,3,4,5,6,7}，因为0,2,4,6和8并不互素。
构造$({\mathbb{Z}}_8,{\cdot }_8)$的运算表如下

该运算并不存在逆元，因而不能构成群。

当$n$取素数时， Z n ∗ = { 1 , 2 , … , n − 1 } \mathbb{Z}^*_n=\{1,2,\dots,n-1\} Zn∗​={
1,2,…,n−1}，因为n必然与比其小的所有数互素。

异或群

定义群$({\mathbb{Z}}_n,\oplus )$，其中 Z n = { x ∣ 0 ≤ x < n , x ∈ Z } \mathbb{Z}_n=\{x|0\le x<n,x\in\mathbb{Z}\} Zn​={
x∣0≤x<n,x∈Z}，$\oplus$指异或运算，群$({\mathbb{Z}}_4,\oplus )$的运算表为

显然此时，单位元为0，任何元素的逆元为其自身。

伽罗华域

伽罗华域也称为有限域，域$(R,+,-,\cdot ,÷)$由运算元素集合和四则运算组成，由于减法、除法分别和加法、乘法是逆运算关系，只需要关注加法和乘法即可。对于加法来说，每个元素要求有对应的加法逆元；对于乘法来说，除0以外的每个元素要求要有对应的乘法逆元。关于群、环、域的概念进一步了解可阅读这篇博客。

伽罗华域$GF(q)$表示

$q$指有限域的阶，在有限域中阶等于元素个数，有限域的阶通常是素数$P$或是素数幂$P^W$，即$q=P或P^W$。

有限域$GF(P)$

$GF(P)$被称为P阶素数域，$P$为素数。运算元素的集合为${\mathbb{Z}}_p$，加法和乘法运算要在模p上进行，即此时的加法和乘法运算分别为${+}_p,{\cdot }_p$。在$GF(P)$上$a\equiv b\mathrm{mod}P$与a=b相同，这意味着$a=b\to a=kn+b,k\in \mathbb{Z}$。当$P$为素数时，显然所有大于0小于p的整数和是互素的，根据上面介绍的模n乘法群的概念，显然除去0以外，每个元素都能找到其逆元。
对于$GF(2)$，仅包含了元素0和1,加法表为

乘法表为

有限域$GF(P^w)$

当$n>1$时，$GF(P^w)$可以表示为系数属于$GF(P)$域上的多项式，$w$表示多项式不能超过的阶。举个栗子，对于$GF(3^4)$，来说其包含了多项式$0,1,2,x+1,x+2,2x,2x+1,2x+2,x^2+x,x^2+x+1,\cdots ,2x^3+2x^2+2x+2$,即多项式系数为0,1,2，此时$w=4$，多项式阶数不能超过4，符合这两个条件的多项式个数为$P^w$，注意这里的有限域的集合中的元素可以看成多项式，即加法和乘法是指多项式的加法和乘法，特殊之处在于对于计算后的各项系数需要取模$P$，同时对整体还需要取模$f(x)$。参考$GF(P)$的取模方法，这里取的模$f(x)$也应该是多项式，关于多项式的运算规则可以查看这篇博客。接下来我会举出大量栗子帮助理解。
对于$GF(2^3)$，其包含了元素有8个分别为$0,1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1$, 一些文章中多项式会用二进制进行表示，即8个元素也可以对应表示为000,001,010,011,100,101,110,111。
其可取的模为$x^3+x^2+1$,$x^3+x+1$，模同样也可用二进制表示1101,1011.
在有限域$GF(2^w)$中，需要对多项式各项系数取模2
$(x+1{)}^2=x^2+2x+1\equiv x^2+1$，这里对$2x$的系数取模，$2\equiv 0\mathrm{mod}2$
$3x^2-x-1\equiv x^2+x+1$，这里对$3x^2$的系数取模，$3\equiv 1\mathrm{mod}2$
$(x+1{)}^3=x^3+3x^2+3x+1\equiv x^3+x^2+x+1$
在有限域$GF(3^w)$中，需要对多项式各项系数取模3
$(x+1{)}^2=x^2+2x+1\equiv x^2+2x+1$
$3x^2-x-1\equiv 2x+2$
$(x+1{)}^3=x^3+3x^2+3x+1\equiv x^3+1$
接下来需要进行取模，模为$f(x)$，这个模等同于不可约多项式或是本原多项式，本原多项式是不可约多项式的特例，即在不可约多项式中除去最高阶的项，剩余项的阶最小那个多项式定义为本原多项式。希望对不可约多项式和本原多项式有更多了解的，可以参考这篇博客。对于$GF(2^3)$，模可以取$x^3+x^2+1$或$x^3+x+1$，这两个多项式也就是阶为3的不可约多项式。
再列举几个计算案例
在$GF(2^3)$，模取$x^3+x+1$ ，计算$4x^5+3x^3+1\mathrm{mod}{x}^3+x+1$
回想整数除法$11/5=2余1$，$11\equiv 1\mathrm{mod}5$
$\frac{\left(4x^5+3x^3+1\right)}{x^3+x+1}=4x^2-1+\frac{-4x^2+x+2}{x^3+x+1}$
那这里余项为$-4x^2+x+2$，即$4x^5+3x^3+1\mathrm{mod}{x}^3+x+1\equiv -4x^2+x+2\mathrm{mod}{x}^3+x+1（注意这里是对各项系数取模2，与多项式的模无关）\equiv x\mathrm{mod}{x}^3+x+1$
或者先对$4x^5+3x^3+1$系数先取模2，即$4x^5+3x^3+1=x^3+1$
$\frac{x^3+1}{x^3+x+1}=1+\frac{-x}{x^3+x+1}$，对余项$-x$的系数$-1$取模2，结果为$x$。
再举一个例子
$(1+2m)x^2+(1+2n)x\equiv x^2+x\mathrm{mod}{x}^3+x+1$，其中$m,n\in \mathbb{Z}$