type
status
date
slug
summary
tags
category
icon
password
Sub-item
Last edited time
Oct 28, 2023 10:44 AM
Parent item
领域
域的性质
在加法和乘法上具有封闭性。也就是说对域中的元素进行加法或乘法运算后的结果仍然是域中的元素。有一点要注意，域里面的乘法和加法不一定是我们平常使用的乘法和加法。可以把 C 语言中的与运算和异或运算分别定义成加法和乘法。但习惯上，仍然使用符号 + 和 * 表示加法和乘法运算。
本文会简单介绍一些有关群和域的概念，不过对于概念的定义，本文写得并不严谨，所以对于这些概念，最好还是配合书或者维基百科一起看吧。
域有单位元和逆元两个概念。
- 单位元
- 对于加法单位元，所有元素加上单位元 ，等于其本身。
- 对应乘法单位元，所有元素乘上单位 ，等于其本身。
加法和乘法运算都有对应的单位元 (这两个单位元一般不同，但都用符号 表示)。单位元就像线性代数的单位矩阵。一个矩阵乘以单位矩阵等于本身。对应地，在域中的单位元有：
- 逆元
逆元就像数学上的倒数，两个元素互为对方的逆元。如果元素 和互为加法逆元，那么就有。若互为乘法逆元，那么就有 a。如果元素 在域中找不到另外一个元素，使得，那么 就没有加法 (乘法) 逆元。
逆元有什么用呢？其实逆元是用于除法运算的。小学的时候老师都会教：除于一个分数就等于乘以该分数的倒数 (分数的倒数就是该分数的乘法逆元)。所以要想除于某个数，可以乘以该数的逆元。
一个集合有加法单位元和乘法单位元，以及每一个元素都对应有加法逆元和乘法逆元，是成为域的必要条件。
需要注意：即使集合里面有元素 0，并且 0 没有对应的乘法逆元，那么该集合也可能是一个域。因为并不要求 0 有乘法逆元。
一个域的例子就是我们平时熟悉的有理数集合，相应的加法和乘法就是我们平时用的加法和乘法。其中，加法的单位元为，有理数的加法逆元就是其相反数。因为(单位元)。乘法的单位元为 ，的乘法逆元是其倒数。因为 。注意这里的元素 并没有乘法逆元。
有限域
有限域，是指域中的元素个数是有限的。
有限域
在密码学中，有限域 是一个很重要的域，其中 为素数。简单来说，就是，因为一个数模 后，结果在之间。对于元素 和 ，那么 和，其结果都是域中的元素。
里面的加法和乘法都是平时用的加法和乘法。的加法和乘法单位元分别是 0 和 1，元素的加法和乘法逆元都很容易理解和求得，这里就不展开讲了，《密码编码学与网络安全》书中有详讲的。求乘法逆元的实现代码如下面所示，具体是使用了类似辗转相除法的方法。
有一个问题，读者可能会疑惑，为什么 一定要是一个素数呢？这是因为当 为素数时，才能保证集合中的所有的元素都有加法和乘法逆元 (0 除外)。
假如 等于 10，其加法和乘法单位元分别是 0 和 1。加法没有问题，所有元素都有加法逆元，但对于乘法来说，比如元素 2，它就没有乘法逆元。因为找不到一个数，使得 等于 1。这时，就不能进行除于 2 运算了。
对于等于素数，那么它就能保证域中的所有元素都有逆元。即，对于域中的任一个元素，总能在域中找到另外一个元素 ，使得 等于 1。这个是可以证明的，利用反证法和余数的定义即可证明，不难。
有限域
现在重点讲一下，特别是 ，因为 8 刚好是一个字节的比特数。
前面说到， ， 得是一个素数，才能保证集合中的所有元素都有加法和乘法逆元 (0 除外)。但我们却很希望 这 256 个数字也能组成一个域。因为很多领域需要用到。 的余数范围就是 0 到 255，但 256 不是素数。小于 256 的最大素数为 251，所以很多人就直接把大于等于 251 的数截断为 250。在图像处理中，经常会这样做。但如果要求图像无损的话，就不能截断。
貌似已经到了死胡同，救星还是有的，那就是 ，其中 为素数。在这里我们只需令 为 2，n 为 8，即。
多项式运算
要弄懂，要先明白多项式运算。这里的多项式和初中学的多项式运算有一些区别。虽然它们的表示形式都是这样的: 。下面是它的一些特点。
- 多项式的系数只能是 0 或者 1。当然对于，如果 p 等于 3，那么系数是可以取：0， 1， 2 的
- 合并同类项时，系数们进行异或操作，不是平常的加法操作。比如 等于 。因为两个系数都为 1，进行异或后等于 0，也可以理解为二进制进位操作。
- 无所谓的减法 (减法就等于加法)，或者负系数。所以， 就等于, 就是。
看一些例子吧。对于。。
那么。 等于。
。
下图是除法，除法得到的余数，也就是 mod 操作的结果。
素多项式(本原多项式)
对于多项式也类似素数，有素多项式。其定义和素数类似，素多项式不能表示为其他两个多项式相乘的乘积。
素多项式模运算
指数小于 3 的多项式有 8 个，分别是 ， ，，，，，，。（注：对应于二进制000，001，010，011，100，101，110，111）对于 来说，其中一个素多项式为 。上面 8 个多项式进行四则运算后 的结果都是 8 个之中的某一个。当然也可以证明这是一个域，所以每一个多项式都是有加法和乘法逆元的 (0 除外)。注意，这些逆元都是和素多项式相关的，同一个多项式，取不同的素多项式，就有不同的逆元多项式。
对于，其中一个素多项式为 。对应地，小于 8 次的多项式有 256 个。其他常用的素多项式：
由素多项式得到的域，其加法单位元都是 0，乘法单位元是 1。
重点来了：
前面讲到了对素多项式取模，然后可以得到一个域。但这和最初的目的有什么关系吗？多项式和没有什么关系。确实是没有什么关系，但多项式的系数确可以组成 这些数。回到刚才的 对应的 8 个多项式，其系数刚好就是 000,001, 010, 011, 100, 101, 110, 111。这不正是 0 到 7 这 8 个数的二进制形式吗？也就是说，它们有一一对应映射的关系。多项式对应一个值，我们可以称这个值为多项式值。
对于 ，取素多项式为 ，那么多项式 的乘法逆元就是。系数对应的二进制分别为 110 和 011。此时，我们就认为对应的十进制数 6 和 3 互为逆元。即使 不能构成一个域，但通过上面的对应映射，0 到 7 这 8 个数一样有对应逆元了 (为了顺口，说成 0 到 7。实际 0 是没有乘法逆元的)。同样，对于也是一样的。所以 0 到 255，这 256 个数都可以通过这样的方式得到乘法逆元(同样，0 是没有乘法逆元的)。
通过本原多项式生成所有(多项式)
中的所有元素(多项式)都可以通过本原多项式生成，设是上的某一个本原多项式，元素产生步骤（多项式运算）是：
- 给定一个初始集合，包含和元素，即，该3个元素也是的前3个元素；
- 将这个集合中的最后一个元素，例如上面初始集合的最后一个元素是，乘以，如果结果的度大于等于，则将结果后加入集合；
- 直到集合个元素，此时最后一个元素乘以再的值等于1。
例如，含有16个元素，本原多项式为，除了外，另外14个符号均由本原多项式生成。 注意到，此时计算，生成结束。
生成元素 | 多项式表示 | 二进制表示 | 数值表示 | 推导过程 |
0 | 0 | 0000 | 0 | ㅤ |
0001 | 1 | ㅤ | ||
0010 | 2 | ㅤ | ||
0100 | 4 | ㅤ | ||
1000 | 8 | ㅤ | ||
x+1 | 0011 | 3 | ||
0110 | 6 | |||
1100 | 12 | |||
1011 | 11 | |||
0101 | 5 | ㅤ | ||
1010 | 10 | ㅤ | ||
0111 | 7 | x | ||
1110 | 14 | ㅤ | ||
1111 | 15 | |||
1101 | 13 | |||
1001 | 9 | |||
1 | 0001 | 1 |
如果从下面的生成元角度来看，第一列就是对生成元进行遍历，例如生成元.
的四则运算
其实，通过前面的讲解，已经可以对进行四则运算了。但计算起来相当麻烦。接下来就是讲解一下怎么用简单的方法进行四则运算，以及编程的实现 。
下面讲解的所有运算，默认的素多项式为 用 表示。的素多项式有多个，但这个经典啊。
加法和减法
加法和减法就是经典的异或运算，没有什么可说的。
乘法
前面的一个多项式相乘例子有说到怎么进行相乘计算，但过于复杂。《密码编码学与网络安全》一书说到了一个计算乘法的技巧。
首先有，。
对于多项式， 有：
如果等于0，那么结果是一个小于8的多项式，不需要再取模计算了。如果等于1，那么通过上面说的技术有：
对于 C 语言来说，通过位移运算符
<<和异或运算，很容易计算。对于 x 的指数高于一次的情况，可以通过递归的形式使用。如：。虽然有上面的技巧，但还是过于复杂。在大量运算中 (比如图像处理)，耗时太多。于是人们就想到了通过查表的形式计算。
生成元
要弄懂查表的原理，得明白一个概念：生成元 g。
如果元素 满足下面的条件，我们就称 为生成元：对于集合中的任何的一个元素，都可以通过元素 的幂得到。并定义 ，假设 为 的逆元，那么还定义。比如，整数集合，都可以由生成元 1 得到。。负数可以通过幂取负数得到。
生成元是域上的一类特殊元素，生成元的幂可以遍历域上的所有元素。假设是域上生成元，那么集合包含了域上所有非零元素。在域中2总是生成元。
将生成元应用到多项式中， 中的所有多项式都是可以通过多项式生成元g通过幂求得。即域中的任意元素，都可以表示为。
下面看一下，怎么将生成元应用到多项式乘法中。
对于 ，有正过程和逆过程。知道 求 是正过程，知道了 反过来求是逆过程。
假设有和 。现在需要求 ，那么就有 。我们只需要：根据 a 和 b，分别求得 n 和 m。然后直接计算 即可。但是并不是真的傻乎乎地通过计算而得到，而是通过查表。这里，构造两个表，正表和反表。正表是知道了指数，求值。反表是知道了值，求指数。接下来要做的就是构造这两个表。为了做除法运算，还要构造逆元表。
在给出三个表的构造代码前，有几个东西要讲一下。
- 虽然生成元的幂次厉害，但多项式 0，是无法用生成元生成的。 等于多项式 1，而不是 0。为什么？逆向思考一下：假如存在 k 使得，那么 等于多少呢？
- 是一个有限域，就是元素个数是有限的，但指数 是可以无穷的。所以必然存在循环。这个循环的周期是 （不能生成多项式 0）。所以当大于等于时，。
对于，有正过程和逆过程。知道指数k求a是正过程，知道值a求指数k是逆过程。
对于乘法，假设，。那么。查表的方法就是根据a和b，分别查表得到n和m，然后查表即可。
因此需要构造正表和反表，在域上分别记为gflog和gfilog。
- gflog是将二进制形式映射为多项式形式，
- gfilog是将多项式形式映射为二进制形式。
注意：多项式0 ，是无法用生成元生成的。等于多项式1，而不是 0。
根据上文的的元素表示，生成gflog表和gfilog表如下：
查表进行乘法和除法运算的例子
在域上的乘法和除法，已知：
乘法：
除法：