笔记整理｜组队学习密码学第六期 密码数学基础：有限域
The following article is from 隐私计算研习社 Author 刘仁章、裴君翎
密码学是一门研究信息安全的学科，其中涉及到许多数学概念，如群、环、域等基本概念。群是一种代数结构，它由一个集合和一个二元运算组成。这个二元运算必须满足以下四个条件：封闭性、结合律、存在单位元和存在逆元，群的一个重要性质是封闭性，这意味着在群中进行的任何操作都不会导致离开群。环是由一个集合和两个二元运算组成，分别是加法和乘法，并满足封闭性、结合律、分配律。域也是由一个集合和加法、乘法两个运算组成，满足封闭性、域中的加法和乘法都满足结合律、存在单位元、加法逆元和乘法逆元。群、环、域通常用于加密算法中。
有限域是元素个数有限的域、有限域的扩张是指将一个有限域在保留运算的情形下扩展为另一个更大的有限域，可以通过添加一个新的元素和构造模多项式剩余类环的方式来实现。分圆多项式在有限域上的分解理论是实现快速数论变换，同态加密中明密文打包技术的基础。
群、环、域、有限域的扩张和分圆多项式在有限域上的分解都是密码学中常用的数学概念，它们在加密算法中起着重要作用，了解这些基本概念可以帮助我们更好地理解密码学的原理和应用。OpenMPC组队学习MPC 第六期，11月4日14:00，我们邀请到了密码学专家、应用数学博士 刘仁章老师，带领大家一起学习密码学基础—有限域。
以下是南开大学的裴君翎关于本期课程的笔记整理，主要分为群环域部分和有限域及其性质部分。
群环域
1. 运算
简单来说，群环域就是一些带运算的集合。我们首先来看一些关于运算的内容。运算实际上是一种映射，是从到的映射：
我们把这种涉及n个操作数的运算称为n元（目）运算，特别地，如果n=2，则称为二元运算。当时，该运算为“定义在上的运算”，也称该运算在集合上是封闭的。二元运算可以简写为。
接下来我们看一个简单的例子，假设集合，它们的运算规则如下表所示：
| 奇 | 偶 | |
|---|---|---|
| 奇 | 奇 | 奇 |
| 偶 | 奇 | 偶 |
这是个什么运算？通过观察我们发现运算结果总是等于第一个操作数，此时我们把这种运算称为“投影运算”：。那么上可以定义多少种不同的二元运算呢？我们可以看出表中有4个“？”，每个“？”处都有奇、偶两种选择，所以一共有种。
再看一个难一点的问题，有多少种本质上不同的二元运算？比如下面这个运算，如果我们把表一中的奇偶对换，即“奇变偶、偶变奇”，那么表一就变成了表二，我们称表一和表二是本质上相同的运算。
这个问题由于时间关系我们不做解答，在群中实际上有两个非常重要的计数工具，一个叫“波利亚计数公式”，另一个叫“伯恩赛德引理”，大家可以去了解一下。
如果中只有一个元素，那么此时果上只能定义一种运算。
2. 群
非空集合及其上定义的运算构成一个群，如果：
运算满足结合律：。（此时该集合关于运算构成一个半群） 存在单位元，使得对任意的成立。（如果(1)、(2)都成立，则称该集合是关于的幺半群） 对任意的，存在逆元，使得。此时，将记做。
特别地，如果运算还满足交换律，即对于任意的，都有，那么称是交换群（abelian）。下面看几个简单的例子：
整数集合在加法下构成一个群，但是它在减法下不构成一个群（结合律不满足）； 模的完全剩余系在加法下构成一个群，模的约化剩余系在乘法下构成一个群； 复数上的所有单位根关于复数乘法构成一个群。
再看一个有点特殊的例子：单元素集合在乘法下构成群吗？即是群吗？答案是肯定的，我们可以通过定义证明，单位元是0，逆元也是0。这里可能有同学有疑问了，那这是不是说明0的乘法逆元是0。与我们之前学的矛盾吗？
不矛盾，因为这里我们的运算规则只有“”这一条，不能把其他结构中的运算规则放在这里（“0在乘法下不可逆”中的“0”实际上是环上的加法单位元，即环的加法单位元在环上的乘法运算下不可逆。另外由于单位元群中只有一个元素，因此只能定义一种运算，不论将其写成“乘法”或者“加法”，本质上都是一样的）。
通常将群中的运算写成加法或者乘法的形式。如果写成加法“+”的形式，那么记。这种情况下表示的是n个相同的
群元素的做加法。如果写成乘法“”的形式，那么记。总的来说，当我们说群结构时，考虑的只是在这个群中所定义的那一种运算。不管在具体的实例化下，及我们熟知的其他代数结构中，还附带了多少其他运算（比如前面例子中的）。
3. 子群
称群是群的子群，如果：
，上的运算限制在集合上就是群上的运算，即对于任意的，。
和总是群的子群，称为平凡子群。对任意的，所有的元素组成的集合构成的一个子群，称为是群中由生成的循环子群，记作。
4. 环
群是只有一种运算的代数结构。环上有两种运算，分别称为加法和乘法。非空集合及定义在其上的运算， 构成一个环，如果：
构成一个交换群。 满足结合律，即 是一个半群。 分配律成立：，。通常，乘法可以简写为。
+运算的单位元记作0，的加法逆记做，称为的负元。
环上有两种运算，那么环上至少有几个元素呢？显然是两个。
如果中的乘法是交换的，即对于任意的，都有，那么称是交换环。即，环的交换性是由乘法决定的。
如果满足对任意的，即是的乘法单位元，那么称是含幺环。通常用1来表示的乘法单位元。
对于，如果存在，使得，那么称是的（左）零因子。不存在零因子的环叫做无零因子环（或）。无零因子环中，使得对所有都成立的最小正整数称为环的特征。如果不存在这样的正整数，则称环的特征为0。无零因子环的特征要么是0，要么是素数。但要注意，如果环的特征是0，则一定是无限环；如果环的特征是，则环不一定是有限环。当其特征为时，
这个等式的证明可以通过组合数公式得到，我们发现中间过程的某些系数一定能被整除，剩下的只有的次幂。
把不存在零因子的含幺交换环叫做整环（domain）。密码学中遇到的整环比较多。环中的所有乘法可逆元称为是的单位（unit）。如果整环中，所有的非零元都是的单位，那么是域。也就是说，域上的乘法满足无零因子、有单位元、交换、非零元可逆。
域首先是一个环，其上有两种运算：加法和乘法。 构成一个交换群，加法单位元是0。， 构成一个交换群，乘法单位元是1。上的乘法和加法通过分配律关联。
有限域及其性质
1. 有限域
有限域是元素个数有限的域，也称为伽罗瓦域（Galois Field）。有限域中至少包含两个元素，即0和1。在模p的加法和乘法运算下，构成了有限域，其特征为p。通常将包含q个元素的有限域记作或者。
考虑p阶有限域的乘法群，根据之前介绍的原根存在性定理，是由模p的原根生成的循环群。这个过程实际上构造出了素数阶的有限域。对于任意，利用模m的剩余类和模m的加法、乘法可以构造出m阶环，那么是否存在任意阶的有限域呢？答案是否定的，有限域的元素个数只能是素数的方幂，即。
2. 域的扩张
域的扩张是将一个域在保持运算的情况下扩展为一个更大的域，这个过程称为域的扩张。域的扩张通常有两种构造方法。第一种是构造剩余类环：假设为n次不可约的首一多项式，即
考虑模f(x)的剩余类环，即所有次数小于n，系数在中的多项式：
R中包含个多项式。由于f(x)不可约，对于任意，。于是存在次数小于n的多项式和，使得
因此，即是环R中的可逆元，从而R关于多项式的加法和乘法（模f(x)）构成一个域，这样我们就构造出了一个阶为的有限域。
在上述构造过程中，关键在于，能够找到一个上的n次首一不可约多项式f(x)。那么，有限域上是否存在任意次的不可约多项式呢？答案是肯定的，证明方法是数出所有n次多项式的个数，再数出可约多项式的个数（可约多项式由低次不可约多项式乘积得到）。
再看一个例子：如何构造4个元素的有限域？首先由于4=2^2，因此需要考虑二元域。是上的不可约多项式。剩余类环
就是4个元素的有限域，其中。令，则其中。这样。需要注意的是，这里不再是有限域上的不可约多项式，因为。从这里可以看出多项式的可约性与（其系数）所在的环/域有关，比如在实数域上不可约，但在复数域上有，其中是虚根单位。但是我们还有另一个结论：多项式的整除关系和所在的域无关。这是因为，如果两个多项式和在域上具有整除关系，即存在使得 ，那么在扩域上，由于,也一定有整除；反之，如果两个多项式和在扩域上具有整除关系，即存在使得，那么根据域的乘法封闭性，也一定有，即在域上，有整除。下面我们再举例说明域扩张的另一种方法。暂时跳开有限域的范畴，考虑有理数域，定义加法、乘法为：，单位元和逆元通过，构造得到。由于，通过添加虚根单位，将进行了域扩张，得到了。类似的还有，其中是上不可约多项式的根。简而言之，通过添加一个不在域中的元素，在原有的加法和乘法的基础上进行扩展，进而实现域的扩张。
接下来我们介绍零化多项式：
需要注意的是，在有理数域中是超越的，即不存在有理数域上的非0多项式使得该多项式以\pi为根。下面回到有限域的例子：对进行扩张。通过在中添加一些元素，使其保持域的运算性质。添加某个不可约多项式的根，如令是的某个根,那么F，在这样的描述中，中的元素看似有无限多个，但实际上由于，因此
可以验证，也构成一个域。如果把写成x，那么可以看到
。前面介绍的这两种域扩张的方法我们都是从素数阶有限域去扩张，实际上，我们也可以从非素数阶的有限域进行扩张，如将F_8扩张成F_{64}，只需要在F_8上添加一个二次不可约多项式的根并按照前面的步骤扩张即可。3. 扩域上的运算
4. 扩域
从集合的角度讲，，从运算的角度来讲，K中的元素关于F中的加法和乘法运算也构成域，那么称K是F的子域，F是K的扩域。如果它们都是有限域，那么F的阶是K的阶的幂次，所以不存在阶为2^3=8的子域。有限域的乘法群是一个阶为的循环群，其生成元也称为域的本原元。需要注意的是，在模p^n的约化剩余系中也有本原元的概念，但二者是很不一样的：是阶为的循环群，模p^n的约化剩余系的阶是。
扩域的性质很多，比较重要的有：
称为共轭元。
5. 同态映射
同态映射指一个代数结构（群、环、域等）到另一个代数结构的保持运算的映射。同态加密的“同态”也是这个意思，即保持运算的。
值得一提的是，同态加密的定义严格来说还要考虑解密函数的作用：语义安全的加密方案一定是概率加密的，同一个明文对应多个密文，所以同态加密要求对加密之后解密的结果和对a、b对应的密文之和进行解密的结果一致。
下面介绍单同态、满同态和同构：
我们再来看看之前提到的有限域与同构的关系：同构意义下，元素个数（阶）为的有限域只有一个。对于n次不可约多项式,,和都是阶为q^n的有限域,于是两者同构。这个结论对于算法实现的加速很有帮助，比如：SM4算法和AES算法的S盒是仿射等价的，核心都是利用有限域逆运算构造的，如果能找到二者之间的同构映射，那么在实现SM4的S盒时，可以将SM4的运算直接转化为AES上的运算，进而利用AES专用的指令集实现加速；另一个例子是椭圆曲线密码体制中，利用椭圆曲线的自同态映射实现加速。再介绍一个特殊的例子：假设和是不可约多项式的两个根，那么在映射下，，如前所述。
6. 有限域上的多项式
所有有限域上的多项式构成一个环，且这个环具有优良的性质：
最后来介绍一下分圆多项式，这类多项式在同态加密、格密码中都有重要应用。
上述是通过分圆多项式在复数域上的分解进行定义的。可以看到是一个首一、次的多项式。通过递推式进行定义：
下面这个式子在格密码和同态加密中很常见，比如在NTT快速实现中非常有帮助：
有了分解之后我们用域上的多项式环的中国剩余定理做一些加速：
分享嘉宾：刘仁章，密码学专家、应用数学博士
笔记整理：裴君翎，南开大学