有限域上多項式及其簡單應用

李一帆

摘 要 本文介紹了近世代數中的域及有限域的基本概念與性質，并探究了有限域中的幾種重要的多項式及其在密碼學領域的簡單應用。

關鍵詞 域 有限域 多項式 簡單應用

中圖分類號：O157.4 文獻標識碼：A

0引言

域是許多數學分支（如代數、代數數論、代數幾何等）研究的基礎，而其中有限域對于探究代數結構及其運用是非常重要的。有限域上多項式在、編碼理論、密碼學、計算機代數和通信系統等許多領域有廣泛應用。

1域和有限域的基本概念

1.1相關定義

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

定義2域中元素的個數為有限時，則稱域為有限域或galois域，記為GF。并把元素個數稱為有限域的階，記為GF（n）。

1.2域的基本性質

（1）數域都是域；（2）域沒有零因子；（3）域的特征只能是素數或無限；（4）有限除環必為域。

2有限域上的幾種常用多項式

2.1有限域上的一元多項式

設n是一非負整數，表達式？

（1）

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

2.2有限域上的不可約多項式

設，非常數。若有，使得，則或為常數（0次多項式），則稱為多項式環中的不可約多項式或中的素元。

2.3有限域上的本原多項式

設是上的n次不可約多項式。若滿足的最小正整數為，則稱為上的本原多項式。

3有限域上多項式在密碼學中的簡單應用

3.1與的乘法比較

設是域上的一個n次不可約多項式，則

例設為3次不可約多項式，則

。

解 若為的一個本原元，則

。

記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中的應用

高級加密標準（AES）使用的有限域，其中為不可約多項式。

在AES中，把每個字節（8bit）看成有限域中的元素，字節對應的多項式為：

則對于有限域，選定不可約多項式，可做以下運算：

（1）加法（字節的異或運算）：兩多項式相加，結果是一個多項式，其系數是兩個元素中對應系數的模2加。

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

（3）乘法：先進行多項式相乘，再將結果模不可約多項式。

例57·83=C1

解

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

任何系數在二元域中并且次數小于8的多項式，利用歐幾里德算法可以計算和使得

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

4結語

本文介紹了近世代數中的域及有限域的基本概念與性質，并探究了有限域中的幾種重要的多項式，如：有限域上的一元多項式，本原多項式，可約多項式，以及其在密碼學領域的簡單應用。總之，有限域上多項式在、編碼理論、密碼學、計算機代數和通信系統等許多領域有廣泛應用。今后，我們還會在更多領域進行探究。

參考文獻

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

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

[3] 王小云，王明強，孟憲萌.公鑰密碼學的數學基礎[M].北京：科學出版社，2015.

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