有限域上多项式及其简单应用

李一帆

摘 要 本文介绍了近世代数中的域及有限域的基本概念与性质，并探究了有限域中的几种重要的多项式及其在密码学领域的简单应用。

关键词 域 有限域 多项式 简单应用

中图分类号：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