密码学数学基础之有限域基础
有一类特殊的环具有比较好的运算性质：可以进行加、减、乘、除四则混合运算，这就是域。包含有限个元素的域称为有限域，在密码学中有着非常广泛的用途。
本文介绍有限域的基本结构和构造方法。
重要前置知识
一个重要的定理：如果p是素数，则剩余类环
是一个域，若n是合数，则剩余类环
有零因子，不是域。
我们已经得到了一种特殊类型的有限域：。
这种有限域可以用来作为构造密码算法的基础，但是有些时候不够，还需要寻找更多类型的有限域。
包含q个元素的有限域用
或者)
来表示。
例子：
多项式
定义1 数域F上的多项式指的是具有如下形式的表达式：
%3Df_%7Bn%7Dx%5E%7Bn%7D%2Bf_%7Bn-1%7Dx%5E%7Bn-1%7D%2B...f_%7B1%7Dx%2Bf_%7B0%7D)
其中x称为未定元，
称为i次项，
称为多项式的系数，所有系数均取自于数域F。未定元x的最高次的系数
不等于0，称n为多项式)
的次数，记作
。
比如
是有理数域上的3次多项式：x%5E%7B6%7D-2x%5E%7B3%7D%2Bi)
是复数域上的6次多项式。
多项式环
数域F上的全体多项式在多项式的加法和乘法下构成了一个环，称为F上的多项式环，记作
，F称为系数域。
当n等于0时多项式是数域F中的一个数，特别地，%3D0)
称为零多项式。一般将
称为多项式的首项，如果
，则称为首一多项式。
比如：
是实数域上的3次首一多项式。
定义2 设%E3%80%81r(x)%E3%80%81s(x)%E3%80%81p(x))
都是数域F上的多项式，则当r(x)%3Ds(x))
且)
不是零多项式时，称整除)
，称作的倍式，是的因式，记作%7Cs(x))
。
定义2 设
带余除法：对于任意一对多项式)
和)
，其中不是零多项式，则一定存在唯一的一对多项式)
和，使得%3DQ(x)d(x)%2Br(x))
。
-
其中
-
这个时候我们也称
最大公因式
定义3 两个多项式、的最大公因式指的是满足下面两个条件的首一多项式)
：
-
且
。
-
若
是
。
求两个多项式的最大公因式有一个标准的算法，我们称为多项式的欧几里得算法，或者辗转相除法。其过程完全类似于求两个整数的最大公因子。
欧几里得算法
-
给定两个多项式
- 每一个余多项式的次数都严格小于除多项式的次数，所以在进行有限步带余除法以后一定会得到余多项式为0。
-
最终计算出的
就是
-
两个多项式的最大公因式也可以表示成它们的组合。给定
。
-
求多项式
定义4 若两个多项式的最大公因式为1，则称它们互素。
定理1 中两个多项式和互素的充分必要条件是存在中的多项式%2Cv(x))
，使得c(x)%2B%20v(x)d(x)%3D1%E2%80%8B)
。
定义5 若数域F上的多项式)
只能被
或者)
整除，其中是数域
中的非零元，则称为不可约多项式，否则称为可约多项式；次数至少为1的首一不可约多项式称为素多项式。
例1 二次多项式%3Dx%5E%7B2%7D%2B1)
在实数域内是不可约多项式，但是在复数域内是可约的。
定理2（唯一因式分解定理）数域F上的任意非零多项式都可以唯一分解为一个常数乘以数域F上的若干素多项式的乘积，即%3Dcp_%7B1%7D%5E%7Br_%7B1%7D%7D(x)cp_%7B2%7D%5E%7Br_%7B2%7D%7D(x)...cp_%7Bs%7D%5E%7Br_%7Bs%7D%7D(x))
。
其中
是数域中的常数，)
为F上的素多项式，
为正整数。
多项式模p(x)环
定义6 设是域F上次数非零的首一多项式，则F上次数小于的多项式全体对于多项式的加法和模乘法构成一个环，称为多项式模环。
定理3 多项式模首一多项式环成为域的充分必要条件是为素多项式。
证明 充分性：若为素多项式，则环中任意非零多项式与互素，存在一组多项式)
和)
，使得p(x)%2Bb(x)s(x)%3D1)
。
-
等式两端同时模
在模
-
必要性用反证法，设
，等式两边同时乘以
，导出矛盾。因此
有限域扩张
对于已知的任何有限域，只要能找到上的一个m次素多项式，就一定能构造出一个新的有限域。
这个新的有限域由上次数小于m的全体多项式组成。
这个新的有限域包含了
个元素。
我们构造出了有限域)
。
例2 从有限域)
构造)
。首先选择上的2次素多项式%3Dx%5E%7B2%7D%2Bx%2B1)
，上的多项式全体模以后得到的有限域为：%3D%5C%7B0%2C%201%2C%20x%2C%20x%2B1%5C%7D)
。
按照系数模2，多项式模运算，可以得到的加法表和乘法表：
有限域元素具有多种表示形式：
- 以GF(4)为例说明有限域元素常见的四种形式
- GF(4)的不同形式
本原元
定义7 若有限域中所有的非零元素都可以表示成某元素的指数形式，则称元素为本原元。
例3 中的
是本原元，根据刚才的表，三个非零元都可以表示成x的不同指数。
例4 )
中的2是本原元，容易计算出：
。所有非零元都表示成了2的不同指数。
定理4 有限域的所有非零元素在乘法下所构成的群是一个循环群。
- 回顾循环群：循环群中的所有元素都可以表示成生成元的指数形式。
- 所以有限域的所有非零元都可以表示成乘法循环群的生成元的指数形式。
- 这个生成元就是有限域的本原元。
定理5 任意有限域都有本原元。
例5 考察%3DGF(2%5E%7B3%7D))
，构造这个有限域需要用上的3次素多项式来进行域的扩张。可以验证%3Dz%5E%7B3%7D%2Bz%2B1)
就是一个素多项式，可以用来进行域的扩张。
离散对数问题
如果已知有限域的本原元
和指数
，计算
是比较容易的。
如果只给了本原元和域中任意非零元素a，要求出k，使得
，没有什么特别有效的算法，特别是在有限域的规模比较大的情况下更是如此。
-
因为
的对数，所以将其称为离散对数问题。
- 基于这个问题可以构造很多公钥密码算法。
