伽罗华域性质简析

伽罗华（伽罗瓦）域名字听起来挺酷的，其实就是有限域。域这个东西由于他能够进行满足加减乘除四则运算，在加密解密、编码解码当中应用非常广泛。但是我们常见的实数域却无法直接在计算机中精确的保存，因此有限域这类能够支持四则运算而且能够用有限的编码精确保存的东西就非常有用了。

（顺带提一句，伽罗瓦这个人的生平很有意思，如果他活久点，说不能成为跟高斯、欧拉一样档次的人。。。）

域

域的定义在各种与离散数学相关的地方都能看到，看上去定义的十分啰嗦，说白了其实就是从有理数抽象出来的一种集合，能加能减能乘能除，满足各种四则运算律。普通的域没啥特别之处，感觉实际上用处不大。

有限域(GF域、伽罗华域)

有限域的性质相比域来说就诱人多了，除了域的通用特点外，他还能够将所有运算的值在有限的数位内表示出来。这对数的保存而言特别有利。 常见的有限域当然就是模素数域了，比如模7域GF(7)=\{0,1,2,3,4,5,6\}，这类域能够生成阶数为指定素数的域。但是很多情况下，我们需要域的阶数不是一个素数，而是一个类似于2^n之类的数，比如一个字节的大小2^8，如果能把这个范围的数用一个域来映射，那对很多计算是特别有帮助的。在要求不严格的情况下，我们当然可以弃掉一些信息，截取一个小一点的素数，比如对于256来说，我们可以选择251，来构成模251域。不过毕竟信息有丢失，我们需要一个更加方便安全的方法。

GF(2^n)域

这个域的出现解决了上面的问题，他的阶数恰巧适应了二进制表示，比如常见的GF(2^8)就能正好表示一个字节的数。他的基本思想就是把数字映射到一个多项式，把他的四则运算变成多项式之间特殊的四则运算。

映射方法

对于GF(2^8)来说，一个8bit的二进制数就直接按照各个位上的值依次放在x^i的系数上(显然这个多项式各个位上的系数只能是0或1)。比如5的二进制表示是101，那么他对应的多项式就是x^2+1。

多项式计算

多项式的计算是问题解决的核心，普通的多项式以及正常的四则运算显然不是一个域。为了保证多项式能够构成域，我们特地设计了下面的运算。

正如整数集合不能构成域，但是模素数集合却能构成域一样。普通的多项式不能构成域，但是模素数多项式却能构成域。所谓的素数多项式，就是指不能被因式分解的多项式，这么设计的理由跟模素数域中选用素数的理由一样。对于GF(2^8)，素数多项式的最高项一定是8次，至于低次位的是多少我们并不在意。这个素多项式，我们叫做本源多项式。

加减运算：这上面定义的加减运算就是各个位的系数进行异或操作，显然加法跟减法是一个意思。

乘除运算：如果按照加减法的定义直接进行乘除运算的话会比较麻烦，通常的做法是用逆元表进行计算。我们知道有限域的生成元g可以直接用其自身的幂表示整个GF(2^n)域，那么域中的每个元素都可以表示成g^i。我们可以根据生成元g轻松确定这个i，那么他的逆元就是g^(n-i)。这样我么就可以打一个逆元的表，若要求a*b，我们直接去求(a^{-1}*b^{-1})^{-1}即可，只要查三次表。

当然，在具体的运算过程中还有很多细节可以优化，比如乘法过程可以用异或和位移运算来加速等等。

参考资料

Finite Field Arithmetic and Reed-Solomon Coding 有限域GF(2^8)的四则运算及拉格朗日插值 DataMatrix编码2——伽罗华域运算