数学基础 - 有限域

数学基础-有限域

本文填一个之前留下的坑, 在将AES算法的时候, 里面用到了GF(256)的一个有限域, 那一篇文章中, 我并没有对相关运算进行展开描述, 本文将聊一聊有限域相关的知识。

由于个人水平有限, 如果那里说的不对的地方, 还请各位读者指出。

有限域属于抽象代数的内容, 如果去聊完整的抽象代数体系, 东西将会比较多, 有兴趣的读者可以去参考抽象代数的相关书籍, 本篇文章不会去描述的那么深入, 毕竟篇幅有限。

到域这个结构里面, 所附加的性质会越来越多, 对于域来说, 他是环的子集, 而环又是群的子集, 因此下面会从最简单的代数结构开始讲起, 一步一步附加条件一直到域这个结构，描述完域之后, 接下来就会来讲今天的主角 -- 有限域了。

群

在抽象代数中，下面所采用的符号可能和小学学过的加法和乘法是一样的, 但是对于抽象代数而言, 运算不限于普通的算数运算，这一点要注意, 需要关注加法和乘法究竟是如何定义的, 在下文中, 特殊定义的加法和乘法会做说明。

半群

谈到群之前，先来说一下半群的定义吧, 半群S, 记作(S, ), 定义了一个包含二元运算的集合, 这个二元运算采用来表示。只要满足下面的性质, 即可说构成一个半群:

• 「结合律」: 对于G中的任意元素a,b,c 都有 a(bc) = (ab)c成立。

群的定义

群G, 记作(G, ), 定义了一个包含二元运算的集合, 这个二元运算采用来表示, 注意这个表示一个二元运算, 不是, 不是乘号, 不是乘号重要的事情说三遍。

这个二元运算实际上是表示从上面的一个映射关系, 也就是对于G中的每一个有序数对(a, b)通过二元运算得到的新的元素。

如果在这个运算下面, 满足如下三个性质, 这个运算和这个集合即构成一个群:

• 「结合律」: 对于G中的任意元素a,b,c 都有 a(bc) = (ab)c成立。
• 「单位元」: G中存在一个唯一元素e, 对于G中的任意元素a, 都有成立。
• 「逆元」: 对于G中的任意元素a, G中存在唯一的元素使得成立。

其实应该还有第0条性质, 那便这个二元运算封闭, 也就是如果a和b都属于G, 则，我当时学的归结到了第0条, 有的教程也会把群归结为满足四点性质, 有不同的情况需要稍微注意一点。

既然这一篇都开始讲数学了, 下面来证明一下单位元和逆元的唯一性吧, 这篇文章篇幅可能会想对长一点, 我尽量吧这块的内容讲的细一点, 因为后面的密码学可能会经常用到这一块的知识, 就不每次都补充了, 返回来看看这篇文章就好了。

文章很长, 请忍一下。

• 「单位元唯一性证明」

采用反证法, 假设G中存在两个单位元, 分别为e1和e2, 则根据单位元的性质, 我们有

如果e1是单位元, 则有, 同理，如果e2是单位元, 则有, 因此，可以得到e1=e2与假设矛盾，因此单位元唯一。

• 「逆元的唯一性证明」

我们不妨假设对于元素a, 他有两个逆元b和c, 则通过单位元的性质, 我们可以得到如下:

因此，可以得到逆元是唯一的。

对于抽象代数来说, 这个代数结构描述的挺虚无缥缈的, 因此, 下面来看几个群的例子。

• 例1: 对于整数的加法运算(,+ )

来验证一下是否满足群的三个性质吧, 这个运算显然封闭, 以后对于显然封闭的情况就不单独列出来了, 看不出来的将会特殊说明一下封闭性。

• 加法满足结合律, 这个显然成立
• 加法的单位元即为0, 显然也有并且唯一
• 对于任意的元素a, 他的逆元即为-a, 显然也在里面
• 例2: 对于有理数的加法运算(, +)

这个也比较显然, 和上面的差不多, 就不啰嗦一遍了。

交换群

如果G是一个群, 并且G还满足交换律, 则称之为交换群(Abelian group)。

• 「交换律」: 对于G中的任意元素a和b, 都有ab = ba成立。

上面的两个例子, 其实他们也都是交换群, 可能有读者问了, 有没有不是交换群的例子, 那也来举一个吧, 比如所有的行列式为"1"的矩阵构成的集合和矩阵的乘法运算构成一个群。

不妨来证明一下这是一个群, 假设上面的两个矩阵和满足他们的行列式都是1。

• 封闭性证明

由, 显然有

• 结合律

对于所有矩阵都有结合律, 特别的对于行列式为1的矩阵自然也有结合律。

• 单位元

显然单位矩阵的为1, 因此也满足。

• 逆元

, 显然有，因此逆元也在里面。

我们知道, 一般的矩阵乘法是不满足交换律的，因此这个构成一个群，但是不构成阿贝尔群。

循环群

我们定义求幂运算即为重复运用群当中的运算, 特别的, 如果群中的任意一个元素都可以表示为群中某个元素的幂，我们称这个群为循环群, 这个元素即为生成元。

环

环R, 记做(R, +, ), 这个是有两个二元运算的集合, 这两个二元运算分别被称之为加法和乘法, 对比一下群, 群里面是只有一个二元运算, 下面来看一下构成环的条件:

• 对于加法运算R构成一个交换群, 一般情况下用"0"表示加法的单位元, 用"-a"表示a在加法当中的逆元
• 乘法结合律: 对于R中的任意元素a, b, c有a(bc) = (ab)c成立
• 分配率: 对于R中的任意元素a, b, c，满足下面的式子恒成立:

a(b + c) = ab + ac
(a + b)c = ac + bc

其实这个可以这么去理解, 环是对于加法运算构成一个交换群, 对于乘法运算构成一个半群，同时加法和乘法满足结合律。

环的例子也不少, 在整数的上面的加法和乘法运算即构成一个环, 其他例子请读者自行脑补一下吧。

交换环

如果R构成一个环, 同时对于乘法满足「交换律」, 则我们称这个环为交换环。

整环

如果一个交换环, 同时满足下面的两个条件:

• 「乘法单位元」: 在R中存在元素1, 使得对于R中的任意元素a, 有a1 = 1a = a成立
• 「无零因子」: 如果R中元素a, b 如果ab = 0, 则必有a = 0或者b = 0

可以发现在整数里面的乘法和加法运算构成一个整环, 这个比较显然, 就不在这里证明了，有兴趣读者可以自行证明一下。

域

介绍完了前面的知识，终于来到了本文的重点, 域了, 域F, 记做(F, +, )，同样是一个具有两个二元运算的集合，如果满足以下性质, 则构成一个域:

• F构成一个整环
• 「乘法逆元」: 对于F中除了0之外的任意元素a, 都有使得成立。

简单来说, 也就是对于F中的加法运算构成一个交换群, 对于F中除了0之外的元素对于乘法运算也构成一个交换群。举一个简单的例子，对于实数R上的加法和乘法运算即构成一个域。

有限域

在上面所提到的例子当中, 集合F都是无限集, 对于密码学或者计算机当中，无限基本上是不太可能的, 因此在密码学当中，需要关注的还是有限域, 也就是集合元素个数是有限的域。

敲重点, 上面所补充的知识只是为了下面的内容便于理解, 真正在密码学当中用到的多的还是下面的内容。我上面啰嗦了半天，可能读者看着都烦了，不妨坐下来喝口水，来看下面的内容。

对于一个有限域来说，元素个数只可能是下面两种情况, 要么元素个数是素数, 要么元素个数是素数的幂的形式, 即为, 这里GF是Galois Field, 是第一位研究有限域的数学家名字来命名的。

阶为p的有限域

给定一个素数p, 元素个数为p的有限域GF(p)内定义为整数{0, 1, ..., p-1}构成的集合, 运算为模p的加法和乘法。

下面来看一个最简单的有限域的例子GF(2), 这个域里面只有两个元素{0, 1}, 正好计算机当中的二进制也是只有0和1，下面来看一下在这个域当中的加法和乘法运算吧，如下图所示:

GF(2)上面的运算

可以看出加法等价于异或运算，而乘法等价于逻辑与运算。

GF(p)当中的乘法逆元

首先，来先回顾一下小学学过的求解两个数的最大公约数的算法(「欧几里得算法/辗转相除法」)。

• 「欧几里得算法简介」

欧几里得算法是数论当中一个非常基本的例子，相信各位读者大佬们学习编程语言的程序大概率也写过这个算法, 所以这块如果对这个算法比较熟悉的读者大佬, 可以直接跳过这块。

这里，我们只考虑在自然数集()上面的运算，暂时不考虑负数的运算，实际在计算机当中也不太会遇到负数的运算。首先来看一下最大公约数的定义吧，a和b的最大公约数是指的同时能够整除a和b的最大整数，然后我们来看一下如何去找到这个最大公约数。

1. 为了求得a和b的最大公约数，不妨假设, 如果不满足交换一下a和b的顺序就好了。
2. 利用带余除法，b除a可以表示为:

3. 这里余数有两种情况，先来看第一种，即的情况，这种情况下也就是说a是b的倍数, 此时最大公约数也就是b了，因此有
4. 另一个情况，也是最常见的情况, 即, 在这种情况下，可以知道最大公约数一定整除, 由已知d|a, 并且d|b, 那么一定有, 也就是。
5. 首先来看一下的值, 通过第四条，我么知道并且, 那么对于b和的任意一个公因子c， 都有, 因为c被a和b整除，因此我们可以得到, 其中d是a和b的最大公约数, 因此, 我们可以得到, 这个式子即为欧几里得算法的整个核心。因为有一个前提的假设, 因此经过有限次的迭代之后这个算法一定会终止, 有关这个算法的其他正确性证明以及算法的复杂度证明，在本文中就不详细展开了，有兴趣的读者可以参考相关资料。

欧几里得算法流程图

这里，具体欧几里得算法的代码我这就不贴出来了，相信大佬们自己应该是都会写的吧。

接下来聊一聊扩展的欧几里得算法，这个算法为接下来求解有限域当中的乘法逆元当中使用，我们知道，欧几里得算法可以求得两个数的最大公约数，也就是, 我们观察计算的每一步，可以得到:

观察右边的式子，我们可以的带 , 其中 ， 。带入即可得到 , 假设 , 可以得到, ，因此我们最终可以得到下面的一个式子:

其中x和y的符号相反, 这便是扩展的欧几里得算法，理解了这个，接下来就可以看看GF(p)当中的乘法逆元了。

在GF(p)当中的乘法逆元，即满足, 那么如何求得这个乘法逆元呢，这就要用到小学学过的求解最大公约数的算法，欧几里得算法了，我们知道如果a和b互素, 那么他们的最大公约数为1，也就是，之后我们可以得到:

然后，两边同时对于a取模，可以得到:

也就是可以得到，最后这里的y也就是我们需要求的逆了。

多项式运算

在讲之前，首先要聊一下有关多项式的运算，这里只考虑一元多项式。

普通的多项式运算

一个简单的n次多项式(n  0)可以表示为:

其中，是某个指定数集上面的元素，该数集称之为系数集，并且, 我们称f(x)是定义在系数集S上面的多项式。

零次多项式成为常数多项式，仅仅包含系数集里面的一个元素，如果, 那么对应的n次多项式就被称为首1多项式。

同样的，多项式的运算也包含加法和乘法，这些运算实际上是吧变量x当成集合中的一个元素来定义的, 下面来看一下多项式当中的加法和乘法运算, 假设有两个多项式, 其中。

• 加法运算

• 乘法运算

系数在中的多项式运算。

特别的，我们考虑多项式的系数a在有限域F上，称为域F上的多项式。为什么这个系数要在域上定义呢, 还记得之前提到过的关于域的定义里面对于乘法来说，对于非0元元素都可逆这一条性质吗，因此对于系数在域上的多项式，我们可以定义除法运算，也就是说除法运算可以定义为求解系数的逆元的过程，举一个例子，如果多项式系数为整数集合, 那么计算这样是没有办法计算的, 因为5/3在整数上面是不封闭的，当然定义在实数上面这是可以的, 但是实数在加法和乘法上面也是构成一个域的，或者说我们定义在GF(7)上面，同样我们可以得到这是因为在之前提到的求逆的运算，即可得到这个关系。有了除法运算，和整数的带余除法一样，我们同样可以得到多项式的带余除法的定义:

同样的如果我们可以说整除, 和整数的类似。

对于密码学来说，其实最有用的还是在GF(2)上面的多项式，这是为什么呢，上文说到过GF(2)上面的运算，加法等价于异或运算，乘法等价于逻辑与运算，并且模2的加法和减法是等价的，在计算机当中，逻辑运算是非常常见和简单的运算，因此系数在GF(2)上面的运算是我们接下来讨论的重点。

首先开看一下什么是不可约多项式，在域F上的多项式被称为不可约的，当且仅当不能表示为两个多项式的乘积。和整数类似，我们称这个多项式为素多项式。

来看一个例子，考虑GF(2)上的多项式, 这个在实数上面显然是不可以因式分解的，但是这次我们考虑是在GF(2)上面的运算(学了密码学一定要注意运算的集合，要不好多东西推出来可能是错的)。我们有因此这个多项式是可约的，下面再来一个不可约多项式的例子，, 这个显然是不能拆成两个因式的乘积的，因此是不可约的。

求解最大公因式

在整数当中，我们讨论了如何计算两个数字的最大公约数，类似的，我们可以再多项式当中计算两个多项式的最大公因式，两个多项式的最大公因式满足下面两个条件:

• c(x)可以同时整除a(x)和b(x)
• a(x)和b(x)的任何因式都是c(x)的因式

同样的，我们依然可以采用欧几里得算法来计算两个因式的最大公因式:

只不过，这里的运算从整数上扩展到了多项式上面，这个我就不带着大家手算一个了，实话说，我手算成功的概率也不高，正常不是在考试中，大家用程序计算一下就好了，考试的时候，也只能靠自己手算了。

有限域GF()

对于密码学来说，其中最终要的一个有限域也就是GF()了，这个有限域有得天独厚的优越性，举个简单的小栗子。

大家都知道，计算机一个字节有8位, 那么他可以表示的数也就是从0到255, 我们如果要对8位数据进行处理，并且可能用到除法，首先想到的是采用上面的运算，可惜的是这个东西如果用模运算来说，他不构成一个域，也就是并非所有的元素都有逆元，然后如果我对模运算他情有独钟，那么我只能去用这一个域了，但是这个造成了251~255不能用了，每次都少这几个，如果信息量大的话，这个浪费就很可观了。这里如果采用GF()这个域，那就不会有这种问题了，完美的应用到了所有的空间。

来看一下这个域的构成集合，我们知道，对于一个多项式，可以表示为下面的形式:

其中, 因此S一共有个不同的多项式。

来看一下之前AES当中的例子，它使用了GF()这个有限域上面的运算，他的不可约多项式为, 具体设计多项式的运算在这里就不带着大家算了。

对于多项式求解乘法的逆元，同样的也可以采用扩展的欧几里得算法来进行求解，只是把原来的数字换成多项式就可以了，在这里也不去详细的解释这个方法了，如果有不明白的可以去类比整数上面的运算，基本上是一致的。

小结

本文介绍了有限域的一些简单的相关知识，由于这一块的体系知识确实有点多，而且抽象代数这个东西吧，他也很不实在，如果不去说例子的话，也可能不太好去理解，但是这个定义出来的结构确实是良好的，我个人也对这个所研究的不是特别的深入，因为太深入的我也不太能够理解，这个属于密码学所要了解的基本的知识，如果说AES不去了解有限域，其实也能够去理解那个算法，就是定义了一些表，可以不去完整的理解这个是怎么来的，但是后面如果要去了解非对称加密比如DH的密钥交换协议等等，如果不去了解有限域这些知识，可能理解起来就有点费劲了。本文确实写得挺长而且比较的枯燥，等我想到更好的理解方式，也可能会重新再次的梳理一下这块的知识，能读到这里的读者，说明比较有毅力了，感谢大家。