笔记整理｜组队学习密码学第六期 密码数学基础：有限域

1. 运算

简单来说，群环域就是一些带运算的集合。我们首先来看一些关于运算的内容。运算实际上是一种映射，是从到的映射：

我们把这种涉及n个操作数的运算称为n元（目）运算，特别地，如果n=2，则称为二元运算。当时，该运算为“定义在上的运算”，也称该运算在集合上是封闭的。二元运算可以简写为。

接下来我们看一个简单的例子，假设集合，它们的运算规则如下表所示：

这是个什么运算？通过观察我们发现运算结果总是等于第一个操作数，此时我们把这种运算称为“投影运算”：。那么上可以定义多少种不同的二元运算呢？我们可以看出表中有4个“？”，每个“？”处都有奇、偶两种选择，所以一共有种。

再看一个难一点的问题，有多少种本质上不同的二元运算？比如下面这个运算，如果我们把表一中的奇偶对换，即“奇变偶、偶变奇”，那么表一就变成了表二，我们称表一和表二是本质上相同的运算。

这个问题由于时间关系我们不做解答，在群中实际上有两个非常重要的计数工具，一个叫“波利亚计数公式”，另一个叫“伯恩赛德引理”，大家可以去了解一下。

如果中只有一个元素，那么此时果上只能定义一种运算。

2. 群

非空集合及其上定义的运算构成一个群，如果：

1. 运算满足结合律：。（此时该集合关于运算构成一个半群）
2. 存在单位元，使得对任意的成立。（如果(1)、(2)都成立，则称该集合是关于的幺半群）
3. 对任意的，存在逆元，使得。此时，将记做。

特别地，如果运算还满足交换律，即对于任意的，都有，那么称是交换群（abelian）。下面看几个简单的例子：

• 整数集合在加法下构成一个群，但是它在减法下不构成一个群（结合律不满足）；
• 模的完全剩余系在加法下构成一个群，模的约化剩余系在乘法下构成一个群；
• 复数上的所有单位根关于复数乘法构成一个群。

再看一个有点特殊的例子：单元素集合在乘法下构成群吗？即是群吗？答案是肯定的，我们可以通过定义证明，单位元是0，逆元也是0。这里可能有同学有疑问了，那这是不是说明0的乘法逆元是0。与我们之前学的矛盾吗？

不矛盾，因为这里我们的运算规则只有“”这一条，不能把其他结构中的运算规则放在这里（“0在乘法下不可逆”中的“0”实际上是环上的加法单位元，即环的加法单位元在环上的乘法运算下不可逆。另外由于单位元群中只有一个元素，因此只能定义一种运算，不论将其写成“乘法”或者“加法”，本质上都是一样的）。

通常将群中的运算写成加法或者乘法的形式。如果写成加法“+”的形式，那么记。这种情况下表示的是n个相同的

群元素的做加法。如果写成乘法“”的形式，那么记。总的来说，当我们说群结构时，考虑的只是在这个群中所定义的那一种运算。不管在具体的实例化下，及我们熟知的其他代数结构中，还附带了多少其他运算（比如前面例子中的）。

3. 子群

称群是群的子群，如果：

2. ，上的运算限制在集合上就是群上的运算，即对于任意的，。

和总是群的子群，称为平凡子群。对任意的，所有的元素组成的集合构成的一个子群，称为是群中由生成的循环子群，记作。

4. 环

群是只有一种运算的代数结构。环上有两种运算，分别称为加法和乘法。非空集合及定义在其上的运算， 构成一个环，如果：

1. 构成一个交换群。
2. 满足结合律，即 是一个半群。
3. 分配律成立：，。通常，乘法可以简写为。

+运算的单位元记作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，因此需要考虑二元域。是上的不可约多项式。剩余类环

下面我们再举例说明域扩张的另一种方法。暂时跳开有限域的范畴，考虑有理数域，定义加法、乘法为：，单位元和逆元通过，构造得到。由于，通过添加虚根单位，将进行了域扩张，得到了。类似的还有，其中是上不可约多项式的根。简而言之，通过添加一个不在域中的元素，在原有的加法和乘法的基础上进行扩展，进而实现域的扩张。

接下来我们介绍零化多项式：

需要注意的是，在有理数域中是超越的，即不存在有理数域上的非0多项式使得该多项式以\pi为根。下面回到有限域的例子：对进行扩张。通过在中添加一些元素，使其保持域的运算性质。添加某个不可约多项式的根，如令是的某个根,那么F，在这样的描述中，中的元素看似有无限多个，但实际上由于，因此

可以验证，也构成一个域。如果把写成x，那么可以看到

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快速实现中非常有帮助：

有了分解之后我们用域上的多项式环的中国剩余定理做一些加速：

隐私计算头条周刊（11.13-11.19）

基于隐私计算的电力数据共享技术系统解决方案及应用

一种基于隐私计算的数据交易模式研究

2023年隐私保护领域的现状和未来

加入我们丨OpenMPC社区招募实习生