有限域

有限域，又称Galois 域，是一类元素有限的域，最常见的有限域是模素数的同余类。

性质

对于域$K$而言，

1. 它的特征总是一个素数$p$；
2. 它的阶总是一个素数的幂，因为它总是一个同构于$Z/pZ$的域上的线性空间，即它的阶为$p^k$，其中$k$是这个空间的维数；
3. 它是多项式$f(x) = x(x^{p^n-1}-1)$的分裂域；
4. 对于$\forall x,y\in K$，满足$(x+y)^{p}=x^{p}+y^{p}$，因为显然$C_{p}^{1}x^{p-1}y=C_{p}^{p-1}xy^{p-1}$，于是根据二项式定理得证.

应用

AES 加密算法

Galois 域是 AES 加密算法的核心，后文将默认读者掌握必要的计算机相关知识.

记阶为$p^n$的有限域为$GF(p^{n})$. 在 AES 算法中，我们经常使用$GF(2^{8})$（即一个字节），其中：

• 元素定义为$\mathbb {Z} /2\mathbb {Z}$上的多项式；
• 加法定义为对应系数做异或运算；
• 本原多项式（即素多项式）类似素数，是不能被域中任意两个非单位元相乘所得的多项式，记作$P(x)$. 在$GF(2^{8})$常使用$x^{4}+x^{3}+x^{2}+1$；
• 乘法的定义较为复杂，结果需要模本原多项式处理：由于乘法可能出现高于7次项的存在，因此需要处理，以八次方为例：$x^{8}\mod P(x)=P(x)-x^{8}=x^{4}+x^{3}+x^{2}+1$；由于$GF(2^{8})$满足乘法对加法的交换律，因此只需考虑最简单的情况：$xF(x)=a_{0}x+a_{1}x^{2}+a_{2}x^{3}+a_{3}x^{4}+a_{4}x^{5}+a_{5}x^{6}+a_{6}x^{7}+a_{7}x^{8}modP(x)$. $a_{7}=0$无需任何处理；否则将$x^8$替换为$x^{4}+x^{3}+x^{2}+1$即可.

AES 算法的安全性保障就在这里：算法过程中所需的S盒需要用到$GF(2^{8})$中的逆元，构建过程可以被证明具有良好的非线性特点，并刻意避开了不动点.

具体原理也请参见隔壁计算机科学 Wiki.