模運(yùn)算

除法定理
$\mathbb{Z}=\{?,?1,0,1,?\}$為整數(shù)集，對(duì)任何整數(shù)a和任何正整數(shù)n存在唯一整數(shù)q和r，滿足$\{r:0\le r<n,r\in \mathbb{Z}\}$,且$a=qn+r$。稱$q=?a/n?$為除法的商，$??$表示向下取整， $r\equiv a\mathrm{m}\mathrm{o}\mathrm{d}n$為除法的余數(shù)。
簡(jiǎn)單例子
$19\mathrm{m}\mathrm{o}\mathrm{d}11\equiv 8\mathrm{m}\mathrm{o}\mathrm{d}11$
$?7\mathrm{m}\mathrm{o}\mathrm{d}11\equiv 4\mathrm{m}\mathrm{o}\mathrm{d}11$
模運(yùn)算的好處：一些程序進(jìn)行線性運(yùn)算的時(shí)候，由于存儲(chǔ)空間大小是固定的，可能存在結(jié)果溢出的情況，模運(yùn)算可以將$x$結(jié)果始終確定在一個(gè)范圍即$\{x:0\le x<n,x\in \mathbb{Z}\}$內(nèi)，從而避免溢出。

有限群

群$(S,\oplus )$是集合$S$和二元運(yùn)算符$\oplus$組成，顧名思義群中的元素個(gè)數(shù)是有限的。對(duì)于該運(yùn)算應(yīng)該滿足以下性質(zhì)：

• 封閉性：對(duì)于任意$a,b\in S$，有$a\oplus b\in S$。
• 單位元：存在一個(gè)元素$e\in S$，稱$e$為單位元，對(duì)所有$a\in S$，滿足$e\oplus a=a\oplus e=a$。
• 結(jié)合律：對(duì)任意$a,b,c\in S$,有$(a\oplus b)\oplus c=a\oplus (b\oplus c)$。
• 逆元：對(duì)任意$a\in S$，存在$b\in S$，滿足$a\oplus b=b\oplus a=e$。

模n加法群

定義群$({\mathbb{Z}}_n,{+}_n)$，其中${\mathbb{Z}}_n=\{x|0\le x<n,x\in \mathbb{Z}\}$，${+}_n$指在模n上的加法，即$a{+}_{n}b=a+b\mathrm{m}\mathrm{o}\mathrm{d}n$，群$({\mathbb{Z}}_5,{+}_5)$的運(yùn)算表為

${+}_5$01234

0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

在該群中單位元為0，0的逆元為0，1的逆元為4。

模n乘法群

定義群$({\mathbb{Z}}_n^{?},{?}_n)$,其中${\mathbb{Z}}_n^{?}=\{x\in {\mathbb{Z}}_n|gcd(a,n)=1\}$，$gcd(a,n)$表示求a和n的最大公因數(shù)，若兩數(shù)的最大公因數(shù)為1則兩個(gè)數(shù)互素，${?}_n$指在模n上的乘法，即$a{?}_{n}b=a?b\mathrm{m}\mathrm{o}\mathrm{d}n$，群$({\mathbb{Z}}_8^{?},{?}_8)$的運(yùn)算表為

${?}_8$1357

1	1	3	5	7
3	3	1	7	5
5	5	7	1	3
7	7	5	3	1

注意${\mathbb{Z}}_8^{?}=\{1,3,5,7\}=\{0,1,2,3,4,5,6,7\}$，因?yàn)?,2,4,6和8并不互素。
構(gòu)造$({\mathbb{Z}}_8,{?}_8)$的運(yùn)算表如下

${?}_8$01234567

0	0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6	7
2	0	2	4	6	0	2	4	6
3	0	3	6	1	4	7	2	5
4	0	4	0	4	0	4	0	4
5	0	5	2	7	4	1	6	3
6	0	6	4	2	0	6	4	2
7	0	7	6	5	4	3	2	1

該運(yùn)算并不存在逆元，因而不能構(gòu)成群。

當(dāng)$n$取素?cái)?shù)時(shí)，${\mathbb{Z}}_n^{?}=\{1,2,\dots ,n?1\}$，因?yàn)閚必然與比其小的所有數(shù)互素。

${?}_5$1234

1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

異或群

定義群$({\mathbb{Z}}_n,\oplus )$，其中${\mathbb{Z}}_n=\{x|0\le x<n,x\in \mathbb{Z}\}$，$\oplus$指異或運(yùn)算，群$({\mathbb{Z}}_4,\oplus )$的運(yùn)算表為

$\oplus$0123

0	0	1	2	3
1	1	0	3	2
2	2	3	0	1
3	3	2	1	0

顯然此時(shí)，單位元為0，任何元素的逆元為其自身。

伽羅華域

伽羅華域也稱為有限域，域$(R,+,?,?,÷)$由運(yùn)算元素集合和四則運(yùn)算組成，由于減法、除法分別和加法、乘法是逆運(yùn)算關(guān)系，只需要關(guān)注加法和乘法即可。對(duì)于加法來說，每個(gè)元素要求有對(duì)應(yīng)的加法逆元；對(duì)于乘法來說，除0以外的每個(gè)元素要求要有對(duì)應(yīng)的乘法逆元。關(guān)于群、環(huán)、域的概念進(jìn)一步了解可閱讀這篇博客。

伽羅華域$GF(q)$表示

$q$指有限域的階，在有限域中階等于元素個(gè)數(shù)，有限域的階通常是素?cái)?shù)$P$或是素?cái)?shù)冪$P^W$，即$q=P或P^W$。

有限域$GF(P)$

$GF(P)$被稱為P階素?cái)?shù)域，$P$為素?cái)?shù)。運(yùn)算元素的集合為${\mathbb{Z}}_p$，加法和乘法運(yùn)算要在模p上進(jìn)行，即此時(shí)的加法和乘法運(yùn)算分別為${+}_p,{?}_p$。在$GF(P)$上$a\equiv b\mathrm{m}\mathrm{o}\mathrm{d}P$與a=b相同，這意味著$a=b\to a=kn+b,k\in \mathbb{Z}$。當(dāng)$P$為素?cái)?shù)時(shí)，顯然所有大于0小于p的整數(shù)和是互素的，根據(jù)上面介紹的模n乘法群的概念，顯然除去0以外，每個(gè)元素都能找到其逆元。
對(duì)于$GF(2)$，僅包含了元素0和1,加法表為

+01

0	0	1
1	1	$0(1+1=2\mathrm{m}\mathrm{o}\mathrm{d}2\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}2)$

乘法表為

$?$01

0	0	0
1	0	1

有限域$GF(P^w)$

當(dāng)$n>1$時(shí)，$GF(P^w)$可以表示為系數(shù)屬于$GF(P)$等價(jià)域上的多項(xiàng)式，$w$表示多項(xiàng)式不能超過的階。舉個(gè)栗子，對(duì)于$GF(3^4)$，來說其包含了多項(xiàng)式$0,1,2,x+1,x+2,2x,2x+1,2x+2,x^2+x,x^2+x+1,?,2x^3+2x^2+2x+2$,即多項(xiàng)式系數(shù)為0,1,2，此時(shí)$w=4$，多項(xiàng)式階數(shù)不能超過4，符合這兩個(gè)條件的多項(xiàng)式個(gè)數(shù)為$P^w$，注意這里的有限域的集合中的元素可以看成多項(xiàng)式，即加法和乘法是指多項(xiàng)式的加法和乘法，特殊之處在于對(duì)于計(jì)算后的各項(xiàng)系數(shù)需要取模$P$，同時(shí)對(duì)整體還需要取模$f(x)$。參考$GF(P)$的取模方法，這里取的模$f(x)$也應(yīng)該是多項(xiàng)式，關(guān)于多項(xiàng)式的運(yùn)算規(guī)則可以查看這篇博客。接下來我會(huì)舉出大量栗子幫助理解。
對(duì)于$GF(2^3)$，其包含了元素有8個(gè)分別為$0,1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1$
其可取的模為$x^3+x^2+1$,$x^3+x+1$
在有限域$GF(2^w)$中，需要對(duì)多項(xiàng)式各項(xiàng)系數(shù)取模2
$(x+1{)}^2=x^2+2x+1\equiv x^2+1$
$3x^2?x?1\equiv x^2+x+1$
$(x+1{)}^3=x^3+3x^2+3x+1\equiv x^3+x^2+x+1$
在有限域$GF(3^w)$中，需要對(duì)多項(xiàng)式各項(xiàng)系數(shù)取模3
$(x+1{)}^2\equiv x^2+2x+1$
$3x^2?x?1\equiv 2x+2$
$(x+1{)}^3\equiv x^3+1$
接下來需要進(jìn)行取模，模為$f(x)$，這個(gè)模等同于不可約多項(xiàng)式或是本原多項(xiàng)式，本原多項(xiàng)式是不可約多項(xiàng)式的特例，即在不可約多項(xiàng)式中除去最高階的項(xiàng)，剩余項(xiàng)的階最小那個(gè)多項(xiàng)式定義為本原多項(xiàng)式。希望對(duì)不可約多項(xiàng)式和本原多項(xiàng)式有更多了解的，可以參考這篇博客。對(duì)于$GF(2^3)$，模可以取$x^3+x^2+1$或$x^3+x+1$，這兩個(gè)多項(xiàng)式也就是階為3的不可約多項(xiàng)式。
再列舉幾個(gè)計(jì)算案例
在$GF(2^3)$，模取$x^3+x+1$ ，計(jì)算$4x^5+3x^3+1\mathrm{m}\mathrm{o}\mathrm{d}{x}^3+x+1$
回想整數(shù)除法$11/5=2余1$，$11\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}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}$
那這里余項(xiàng)為$?4x^2+x+2$，即$4x^5+3x^3+1\mathrm{m}\mathrm{o}\mathrm{d}{x}^3+x+1\equiv ?4x^2+x+2\mathrm{m}\mathrm{o}\mathrm{d}{x}^3+x+1（注意這里是對(duì)各項(xiàng)系數(shù)取模2，與多項(xiàng)式的模無(wú)關(guān)）\equiv x\mathrm{m}\mathrm{o}\mathrm{d}{x}^3+x+1$
或者先對(duì)$4x^5+3x^3+1$系數(shù)先取模2，即$4x^5+3x^3+1=x^3+1$
$\frac{x^3+1}{x^3+x+1}=1+\frac{?x}{x^3+x+1}$，對(duì)余項(xiàng)$?x$的系數(shù)$?1$取模2，結(jié)果為$x$。
再舉一個(gè)例子
$(1+2m)x^2+(1+2n)x\equiv x^2+x\mathrm{m}\mathrm{o}\mathrm{d}{x}^3+x+1$，其中$m,n\in \mathbb{Z}$

冪多項(xiàng)式 模為$x^3+x^2+1$二進(jìn)制 模為$x^3+x^2+1$多項(xiàng)式 模為$x^3+x+1$二進(jìn)制 模為$x^3+x+1$

0	0	000	0	000
$x^0$	1	001	0	001
$x^1$	$x$	010	2	010
$x^2$	$x^2$	100	$x^2$	100
$x^3$	$x^2+1$	101	$x+1$	011
$x^4$	$x^2$	100	$x^2+x$	110

總結(jié)

以上是生活随笔為你收集整理的伽罗华域（有限域）及其运算规则（包含大量例子）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。