密码学知识思考一之有限域上的计算

关于一些关于近世代数的知识，可以通过https://blog.csdn.net/Stu_YangPeng/article/details/119329168 这篇笔记得到一些介绍。

简单地，只需要理解以下几点就可以了：

1. “代数”这门学科，其底层是“集合”和映射。
2. “代数”这门学科，主要就是研究三个东西：计算对象、运算、以及运算性质（运算律）。在我们研究一些运算律（如交换律、结合律等等）时，其实计算对象和运算究竟是什么并不重要，我们会将其抽象为一个个的符号。
3. 一般而言，数学家主要在研究各种“代数系统”的性质。所谓的代数系统，本质上就是一个包含了大量计算对象的集合S及其对应的计算X的组合。即<S,X>；
4. 通过一系列的对运算性质的规定，数学家们为代数系统定义出了群（Group）、环（Ring）、域（Field）等概念，并发展出了一大堆的特殊的代数系统，比如阿贝尔群。

在了解了以上内容之后，我们应当进一步聚焦在一个特殊的代数系统——“有限域”上。顾名思义，有限域包含两个性质：

1. 其对应的集合内元素数量 有限 ；
2. 是域。也就是说，这个集合对于加法运算而言满足“交换群”的定义，对于乘法而言如若去掉零元也可满足交换群的定义。同时，这个集合满足分配律。

上述性质的第二条是十分繁琐的，幸运的是现在不必了解清楚“交换群”的定义。有限域可以这么理解：有限域就是有限个元素的集合。而无限个元素的集合我们已经很熟悉了，——基于加法和乘法扩展所得到的、我们初中所学的有理数集合，就可以看作是一个无限域。这样我们就为有限域得到了一个直观的理解。

从上述理解中我们可以发现，有限域的最大难点在于：难于构造。难于构造的点在于，我们需要确保 集合内的元素在运算之后的结果也属于这个集合 。对于这一点，一个取巧的方法便是取模。 比如我们构造一个集合S_{5}={0,1,2,3,4}，我们可以发现如果我们把加法运算定义为 a+b mod 5 ,乘法定义为a*b mod 5，那么上述的集合便是一个有限域了，因为怎么计算都超不出这个范畴。

是这样的，这便是第一种典型的有限域，GF(P)={0,1,2,…,P-1}，其中P是一个素数（质数）。

其实AES之类的方法便是建构在GF(P)这样的大素数之上的，不过中间还有一些弯弯肠子。我们知道，计算机里所有的数据都可以用二进制串来表示，加密解密的需求也是对应着这些二进制串。例如，对于一个int8类型的整数，我们可以用类似于01011100这样的二进制串来表示。那么，为了构造二进制串上的有限域，我们应当先考虑二进制串上的加法和乘法操作。为了方便，大家会把这个加法和乘法操作用多项式之间的加法和乘法来表达。这当然只是为了直观和方便。例如上面的那一串，写成多项式便是：0*x^0+1*x^1+…+0*x^7。对于这样的多项式，多项式与多项式之间的模加与模乘便是一个有限域了。其中，每个多项式的系数便等价于GF(P)中的一个数字的二进制串，而多项式计算中所模的多项式的各个系数便是P的二进制的每一位。一般而言，把这种多项式有限域记作GF(2^n)，其中n便是二进制串的位数，一般而言,我们会选一个P>2^n，应该是这样吧？