有限域上多項(xiàng)式及其簡(jiǎn)單應(yīng)用

李一帆

摘 要 本文介紹了近世代數(shù)中的域及有限域的基本概念與性質(zhì)，并探究了有限域中的幾種重要的多項(xiàng)式及其在密碼學(xué)領(lǐng)域的簡(jiǎn)單應(yīng)用。

關(guān)鍵詞 域 有限域 多項(xiàng)式 簡(jiǎn)單應(yīng)用

中圖分類號(hào)：O157.4 文獻(xiàn)標(biāo)識(shí)碼：A

0引言

域是許多數(shù)學(xué)分支（如代數(shù)、代數(shù)數(shù)論、代數(shù)幾何等）研究的基礎(chǔ)，而其中有限域?qū)τ谔骄看鷶?shù)結(jié)構(gòu)及其運(yùn)用是非常重要的。有限域上多項(xiàng)式在、編碼理論、密碼學(xué)、計(jì)算機(jī)代數(shù)和通信系統(tǒng)等許多領(lǐng)域有廣泛應(yīng)用。

1域和有限域的基本概念

1.1相關(guān)定義

定義1 設(shè)R是一個(gè)環(huán)，如果，又有單位元且每個(gè)非零元素都有逆元，則稱R是一個(gè)除環(huán)。可換除環(huán)稱為域。

定義2域中元素的個(gè)數(shù)為有限時(shí)，則稱域?yàn)橛邢抻蚧騡alois域，記為GF。并把元素個(gè)數(shù)稱為有限域的階，記為GF（n）。

1.2域的基本性質(zhì)

（1）數(shù)域都是域；（2）域沒有零因子；（3）域的特征只能是素?cái)?shù)或無限；（4）有限除環(huán)必為域。

2有限域上的幾種常用多項(xiàng)式

2.1有限域上的一元多項(xiàng)式

設(shè)n是一非負(fù)整數(shù)，表達(dá)式？

（1）

其中a0，a1，…，an屬于有限域GF，稱（1）為系數(shù)在有限域GF中的一元多項(xiàng)式。

2.2有限域上的不可約多項(xiàng)式

設(shè)，非常數(shù)。若有，使得，則或?yàn)槌?shù)（0次多項(xiàng)式），則稱為多項(xiàng)式環(huán)中的不可約多項(xiàng)式或中的素元。

2.3有限域上的本原多項(xiàng)式

設(shè)是上的n次不可約多項(xiàng)式。若滿足的最小正整數(shù)為，則稱為上的本原多項(xiàng)式。

3有限域上多項(xiàng)式在密碼學(xué)中的簡(jiǎn)單應(yīng)用

3.1與的乘法比較

設(shè)是域上的一個(gè)n次不可約多項(xiàng)式，則

例設(shè)為3次不可約多項(xiàng)式，則

。

解 若為的一個(gè)本原元，則

。

記0=000=0，1=001=1，x=010=2，x+1=011=3，x2=100=4，x2+1=101=5，x2+x=110=6，x2+x+1=111=7；

則乘法表如表1，乘法表如表2，

由上述表格得出，在中，所有非零元素都有乘法逆元；在中，非零元素2，4和6無乘法逆元。

3.2 有限域在AES中的應(yīng)用

高級(jí)加密標(biāo)準(zhǔn)（AES）使用的有限域，其中為不可約多項(xiàng)式。

在AES中，把每個(gè)字節(jié)（8bit）看成有限域中的元素，字節(jié)對(duì)應(yīng)的多項(xiàng)式為：

則對(duì)于有限域，選定不可約多項(xiàng)式，可做以下運(yùn)算：

（1）加法（字節(jié)的異或運(yùn)算）：兩多項(xiàng)式相加，結(jié)果是一個(gè)多項(xiàng)式，其系數(shù)是兩個(gè)元素中對(duì)應(yīng)系數(shù)的模2加。

（2）加法逆元：的加法逆元是它本身。

（3）乘法：先進(jìn)行多項(xiàng)式相乘，再將結(jié)果模不可約多項(xiàng)式。

例57·83=C1

解

（4）乘法逆元：由于是不可約的，故中任一非零元素都與互素，從而有乘法逆元（即模的逆），這樣中非零元素為除數(shù)的除法總是可以進(jìn)行。

任何系數(shù)在二元域中并且次數(shù)小于8的多項(xiàng)式，利用歐幾里德算法可以計(jì)算和使得

那么有，這說明的逆元素為

4結(jié)語

本文介紹了近世代數(shù)中的域及有限域的基本概念與性質(zhì)，并探究了有限域中的幾種重要的多項(xiàng)式，如：有限域上的一元多項(xiàng)式，本原多項(xiàng)式，可約多項(xiàng)式，以及其在密碼學(xué)領(lǐng)域的簡(jiǎn)單應(yīng)用。總之，有限域上多項(xiàng)式在、編碼理論、密碼學(xué)、計(jì)算機(jī)代數(shù)和通信系統(tǒng)等許多領(lǐng)域有廣泛應(yīng)用。今后，我們還會(huì)在更多領(lǐng)域進(jìn)行探究。

參考文獻(xiàn)

[1] 張禾瑞.近世代數(shù)基礎(chǔ)[M].北京：高等教育出版社，2011.

[2] 林東岱.代數(shù)基礎(chǔ)與有限域[M].北京：.高等教育出版社.2006.

[3] 王小云，王明強(qiáng)，孟憲萌.公鑰密碼學(xué)的數(shù)學(xué)基礎(chǔ)[M].北京：科學(xué)出版社，2015.

[4] 馬鳳麗.有限域上的置換多項(xiàng)式及其在密碼學(xué)中的應(yīng)用[J].南京航空航天大學(xué)，2007.endprint