有一类特殊的环具有比较好的运算性质：可以进行加、减、乘、除四则混合运算，这就是域。包含有限个元素的域称为有限域，在密码学中有着非常广泛的用途。
本文介绍有限域的基本结构和构造方法。

重要前置知识

一个重要的定理：如果p是素数，则剩余类环是一个域，若n是合数，则剩余类环有零因子，不是域。
我们已经得到了一种特殊类型的有限域：。
这种有限域可以用来作为构造密码算法的基础，但是有些时候不够，还需要寻找更多类型的有限域。
包含q个元素的有限域用或者来表示。

例子：
的加法表和乘法表。




多项式

定义1 数域F上的多项式指的是具有如下形式的表达式：

其中x称为未定元，称为i次项，称为多项式的系数，所有系数均取自于数域F。未定元x的最高次的系数不等于0，称n为多项式的次数，记作。
比如是有理数域上的3次多项式：是复数域上的6次多项式。

多项式环

数域F上的全体多项式在多项式的加法和乘法下构成了一个环，称为F上的多项式环，记作，F称为系数域。
当n等于0时多项式是数域F中的一个数，特别地，称为零多项式。一般将称为多项式的首项，如果，则称为首一多项式。
比如：是实数域上的3次首一多项式。
定义2 设都是数域F上的多项式，则当且不是零多项式时，称整除，称作的倍式，是的因式，记作。
带余除法：对于任意一对多项式和，其中不是零多项式，则一定存在唯一的一对多项式和，使得。
  • 其中的次数小于的次数，称为商多项式，称为余多项式。
  • 这个时候我们也称模等于。

最大公因式

定义3 两个多项式、的最大公因式指的是满足下面两个条件的首一多项式：
  • 是和的公共因式，即且。
  • 若是和的公共因式，则一定有。
求两个多项式的最大公因式有一个标准的算法，我们称为多项式的欧几里得算法，或者辗转相除法。其过程完全类似于求两个整数的最大公因子。

欧几里得算法

  • 给定两个多项式，，且的次数不小于的次数，利用多项式的带余除法可得：

  • 每一个余多项式的次数都严格小于除多项式的次数，所以在进行有限步带余除法以后一定会得到余多项式为0。
  • 最终计算出的就是和的最大公因式。
  • 两个多项式的最大公因式也可以表示成它们的组合。给定中的两个多项式和，一定存在中的多项式和，使得和的最大公因式等于。
  • 求多项式和也有一个标准的算法，仍然叫做扩展的欧几里得算法。
定义4 若两个多项式的最大公因式为1，则称它们互素。
定理1 中两个多项式和互素的充分必要条件是存在中的多项式，使得。
定义5 若数域F上的多项式只能被或者整除，其中是数域中的非零元，则称为不可约多项式，否则称为可约多项式；次数至少为1的首一不可约多项式称为素多项式。
例1 二次多项式在实数域内是不可约多项式，但是在复数域内是可约的。
定理2（唯一因式分解定理）数域F上的任意非零多项式都可以唯一分解为一个常数乘以数域F上的若干素多项式的乘积，即。
其中是数域中的常数，为F上的素多项式，为正整数。

多项式模p(x)环

定义6 设是域F上次数非零的首一多项式，则F上次数小于的多项式全体对于多项式的加法和模乘法构成一个环，称为多项式模环。
定理3 多项式模首一多项式环成为域的充分必要条件是为素多项式。
证明 充分性：若为素多项式，则环中任意非零多项式与互素，存在一组多项式和，使得。
  • 等式两端同时模，则在模运算下是等于1的，是的逆元。
  • 必要性用反证法，设不是素多项式，则可以分解为次数较低的两个非零多项式的乘积，等式两边同时乘以的逆并取模，可以得到，导出矛盾。因此是素多项式。

有限域扩张

对于已知的任何有限域，只要能找到上的一个m次素多项式，就一定能构造出一个新的有限域。
这个新的有限域由上次数小于m的全体多项式组成。
这个新的有限域包含了个元素。
我们构造出了有限域。
例2 从有限域构造。首先选择上的2次素多项式，上的多项式全体模以后得到的有限域为：。
按照系数模2，多项式模运算，可以得到的加法表和乘法表：

有限域元素具有多种表示形式：
  • 以GF(4)为例说明有限域元素常见的四种形式

  • GF(4)的不同形式

本原元

定义7 若有限域中所有的非零元素都可以表示成某元素的指数形式，则称元素为本原元。
例3 中的是本原元，根据刚才的表，三个非零元都可以表示成x的不同指数。
例4 中的2是本原元，容易计算出：。所有非零元都表示成了2的不同指数。
定理4 有限域的所有非零元素在乘法下所构成的群是一个循环群。
  • 回顾循环群：循环群中的所有元素都可以表示成生成元的指数形式。
  • 所以有限域的所有非零元都可以表示成乘法循环群的生成元的指数形式。
  • 这个生成元就是有限域的本原元。
定理5 任意有限域都有本原元。
例5 考察，构造这个有限域需要用上的3次素多项式来进行域的扩张。可以验证就是一个素多项式，可以用来进行域的扩张。
中的7个非零元构成了乘法循环群，因为7是一个素数，所以除了单位元之外的其它6个元素都可以作为生成元，也就是本原元。取本原元为z：
，，，，，，。

离散对数问题

如果已知有限域的本原元和指数，计算是比较容易的。
如果只给了本原元和域中任意非零元素a，要求出k，使得，没有什么特别有效的算法，特别是在有限域的规模比较大的情况下更是如此。
  • 因为相当于以为底的的对数，所以将其称为离散对数问题。
  • 基于这个问题可以构造很多公钥密码算法。