1）域的概念

参考《密码编码学与网络安全》这书的有限域一章。形象地说，域有这样一个性质：在加法和乘法上具有封闭性。也就是说对域中的元素进行加法或乘法运算后的结果仍然是域中的元素。有一点要注意，域里面的乘法和加法不一定是我们平常使用的乘法和加法。可以把C语言中的与运算和异或运算分别定义成加法和乘法。但习惯上，仍然使用符号+ 和 * 表示加法和乘法运算。

2） 域中单位元和逆元两个概念

　　加法和乘法运算都有对应的单位元(这两个单位元一般不同，但都用符号e表示)。单位元就像线性代数的单位矩阵。一个矩阵乘以单位矩阵等于本身。对应地，在域中的单位元有：对于加法单位元，所有元素加上单位元e，等于其本身。对应乘法单位元，所有元素乘上单位e，等于其本身。

        逆元就像数学上的倒数，两个元素互为对方的逆元。如果元素a和b互为加法逆元，那么就有 a + b = e。若互为乘法逆元，那么就有a * b = e。如果元素a在域中找不到另外一个元素b，使得a+b=e(a*b=e)，那么a就没有加法(乘法)逆元。

　　逆元有什么用呢？其实逆元是用于除法运算的。小学的时候老师都会教：除于一个分数就等于乘以该分数的倒数(分数的倒数就是该分数的乘法逆元)。所以要想除于某个数，可以乘以该数的逆元。

　　一个集合有加法单位元和乘法单位元，以及每一个元素都对应有加法逆元和乘法逆元，是成为域的必要条件。需要注意：即使集合里面有元素0，并且0没有对应的乘法逆元，那么该集合也可能是一个域。因为并不要求0有乘法逆元。

例子：

　　一个域的例子就是我们平时熟悉的有理数集合，相应的加法和乘法就是我们平时用的加法和乘法。其中，加法的单位元为0，有理数a的加法逆元就是其相反数。因为a + (-a) = 0(单位元)。乘法的单位元为1，a的乘法逆元是其倒数。因为a * (1/a) = 1。注意这里的元素0并没有乘法逆元。

有理数是整数（正整数、0、负整数）和分数的统称，是整数和分数的集合。一般用黑体字母Q表示。

3）有限域

有限域，是指域中的元素个数是有限的。

4）有限域GF(p)：

伽罗华域（Galois Field）
Évariste Galois ，伽罗华（也译作伽瓦罗），法国数学家，群论的创立者。用群论彻底解决了根式求解代数方程的问题，而且由此发展了一整套关于群和域的理论。

　　在密码学中，有限域GF(p)是一个很重要的域，其中p为素数。简单来说，GF(p)就是 mod p，因为一个数 模p后，结果在[0, p -1]之间，即该域中有p个元素。对于元素a和b，那么(a+b) mod p和(a*b)mod p，其结果都是域中的元素。GF(p)里面的加法和乘法都是平时用的加法和乘法。GF(p)的加法和乘法单位元分别是0和1，元素的加法和乘法逆元都很容易理解和求得，这里就不展开讲了，《密码编码学与网络安全》书中有详讲的。

求乘法逆元的实现代码如下面所示，具体是使用了类似辗转相除法的方法。

//g_prime就是 GF(p)中的p
int g_prime = 251;
 
int calculateInverse(int x)
{
    int a1 = 1, a2 = 0, a3 = g_prime;
    int b1 = 0, b2 = 1, b3 = x;
 
    while( 1 )
    {
        if( b3 == 0 )
            throw std::logic_error("should not be 0");
 
        if( b3 == 1 )
            break;
 
        int q = a3 / b3;
 
        int t1 = a1 - q*b1, t2 = a2 - q*b2, t3 = a3 - q*b3;
 
        a1 = b1; a2 = b2; a3 = b3;
        b1 = t1; b2 = t2; b3 = t3;
    }
 
    return (b2 + g_prime)%g_prime;
}

View Code

　　为什么p一定要是一个素数呢？

　　这是因为当p为素数时，才能保证集合中的所有的元素都有加法和乘法逆元(0除外)。

        假如p等于10，其加法和乘法单位元分别是0和1。加法没有问题，所有元素都有加法逆元，但对于乘法来说，比如元素2，它就没有乘法逆元。因为找不到一个数a，使得2*a mod 10等于1。这时，就不能进行除于2运算了。

        对于p等于素数，那么它就能保证域中的所有元素都有逆元。即，对于域中的任一个元素a，总能在域中找到另外一个元素b，使得a*b mod p 等于1。这个是可以证明的，利用反证法和余数的定义即可证明，不难。

 5）有限域GF(2^8)：

　　现在重点讲一下GF(2^n)，特别是GF(2^8)，因为8刚好是一个字节的比特数。

        前面说到， GF(p)，p得是一个素数，才能保证集合中的所有元素都有加法和乘法逆元(0除外)。但我们却很希望0到255这256个数字也能组成一个域。因为很多领域需要用到。mod 256的余数范围就是0到255，但256不是素数。小于256的最大素数为251，所以很多人就直接把大于等于251的数截断为250。在图像处理中，经常会这样做。但如果要求图像无损的话，就不能截断。

        貌似已经到了死胡同，救星还是有的，那就是GF(p^n)，其中p为素数。在这里我们只需令p为2，n为8，即GF(2^8)。

 6）多项式运算

　　要弄懂GF(2^n)，要先明白多项式运算。这里的多项式和初中学的多项式运算有一些区别。虽然它们的表示形式都是这样的:f(x) = x^6 + x^ 4 + x^2 + x + 1。下面是它的一些特点。

多项式的系数只能是0或者1。当然对于GF(p^n)，如果p等于3，那么系数是可以取：0， 1， 2的
合并同类项时，系数们进行异或操作，不是平常的加法操作。比如x^4 + x^4等于0*x^4。因为两个系数都为1， 进行异或后等于0
无所谓的减法(减法就等于加法)，或者负系数。所以，x^4 – x^4就等于x^4 + x^4。-x^3就是x^3。

 看一些例子吧。对于f(x) = x^6 + x^4 + x^2 + x + 1。g(x) = x^7 + x + 1。

        那么f(x) + g(x)  = x^7 + x^6 + x^4+ x^2 + (1+1)x + (1+1)1 = x^7 + x^6 + x^4 + x^2。f(x) – g(x)等于f(x) + g(x)。

        f(x) * g(x) =(x^13 + x^11 + x^9 + x^8 + x^7)  +  (x^7 + x^5 + x^3 + x^2 + x)  +  (x^6+ x^4 + x^2 + x + 1) = x^13 + x^11 + x^9 + x^8 + x^6 + x^5+ x^4+ x^3+1。

下图是除法，除法得到的余数，也就是mod操作的结果。

7）素多项式（本原多项式）：

        对于多项式也类似素数，有素多项式。其定义和素数类似，素多项式不能表示为其他两个多项式相乘的乘积。　　

　　伽罗华域的元素可以通过该域上的本原多项式生成。通过本原多项式得到的域，其加法单位元都是 0，乘法单位元是1。

　　以GF(2^3)为例，指数小于3的多项式共8个： 0， 1， x， x+1， x^2， x^2+1， x^2 + x， x^2+x+1。其系数刚好就是000,001, 010, 011, 100, 101, 110, 111，是0 到7这8个数的二进制形式。多项式对应一个值，我们可以称这个值为多项式值。
　　GF(2^3)上有不只一个本原多项式，选一个本原多项式x^3+x+1，这8个多项式进行四则运算后 mod (x^3+x+1)的结果都是8个之中的某一个。因此这8个多项式构成一个有限域。
　　对于GF(2^3)，取素多项式为x^3 + x+1，那么多项式x^2+x的乘法逆元就是x+1。系数对应的二进制分别为110和011。此时，我们就认为对应的十进制数6和3互为逆元。
 
部分 GF（2^w）域经常使用的本原多项式如下：

 8）通过本原多项式生成元素

设P(x)是GF（2^w）上的某一个本原多项式，GF（2^w）的元素产生步骤是： 
1、给定一个初始集合，包含0,1和元素x，即 {0,1,x}； 
2、将这个集合中的最后一个元素，即x，乘以x，如果结果的度大于等于w，则将结果mod P(x)后加入集合；
3、直到集合有2^w个元素，此时最后一个元素乘以x再mod P(x)的值等于1。

例如，GF(2^4)含有16个元素，本原多项式为P(x)=x^4+x+1，除了 0、1外，另外14个符号均由本原多项式生成。
注意到x^14=x^3+1，此时计算x^15=x^14*x=(x^3+1)*x=x^4+x=1，生成结束。

 9）伽罗华域上的运算

加法和减法：

        加法即异或运算

　　 减法即加法

乘法和除法：

伽罗华域上的多项式乘法，其结果需要mod P(x)，可以通过以下方式简化计算。

首先，考虑x^8，x^8 mod P(x) = P(x) – x^8 = x^4 + x^3 +x^2 +1 。

　　对于一般形式的多项式f(x)=a7*x^7 + a6*x^6 + a5*x^5 + a4*x^4 + a3*x^3 + a2*x^2 + a1*x + a0，乘以x得到

x*f(x) = (a7*x^8 + a6*x^7 + a5*x^6 + a4*x^5 + a3*x^4 + a2*x^3 + a1*x^1 + a0*x) mod P(x)

这时有两种情况：
1）a7 == 0，此时结果是一个小于指数小于8的多项式，不需要取模计算。
2）a7 == 1，则将x^8替换为x^4 + x^3 + x^2 +1，而不用进行除法取模计算，结果为：
x*f(x) = (x^4 + x^3 + x^2 +1) + a6*x^7 + a5*x^6 + a4*x^5 + a3*x^4 + a2*x^3 + a1*x^1 + a0*x 

虽然可以通过替换减少除法计算，但还是过于复杂。尤其是在需要大量运算的场合，比如图像处理。于是牛人提出通过查表来减少计算。

10）查表的原理

　　首先介绍一个概念，生成元。
　　生成元是域上的一类特殊元素，生成元的幂可以遍历域上的所有元素。假设g是域GF(2^w)上生成元，那么集合 {g0 ，g1 ， ……，g(2^w-1) } 包含了域GF(2^w)上所有非零元素。

　　将生成元应用到多项式中， GF(2^w)中的所有多项式都是可以通过多项式生成元g通过幂求得。即域中的任意元素a，都可以表示为a = g^k。

　　GF(2^w)是一个有限域，就是元素个数是有限的，但指数k是可以无穷的。所以必然存在循环。这个循环的周期是2^w-1（g不能生成多项式 0）。所以当k大于等于2^w-1时，g^k =g^(k%(2^w-1))。

　　对于g^k = a，有正过程和逆过程。知道指数k求a是正过程，知道值a求指数k是逆过程。 

　　对于乘法，假设a=g^n，b=g^m。那么a*b = g^n* g^m = g^(n+m)。查表的方法就是根据a和b，分别查表得到n和m，然后查表g^(n+m)即可。

　　因此需要构造正表和反表，在GF(2^w)域上分别记为gflog和gfilog。gflog是将二进制形式映射为多项式形式，gfilog是将多项式形式映射为二进制形式。

注意：多项式0 ，是无法用生成元生成的。g^0等于多项式1，而不是 0。

 根据上文的GF(2^4)的元素表示，生成gflog表和gfilog表如下：

查表进行乘法和除法运算的例子
在GF(2^4)域上的乘法和除法，已知2^w-1 = 2^4 -1 = 15：
乘法：
    7 * 9 = gfilog[gflog[7] + gflog[9]] = gfilog[10 + 14]
       = gfilog[24 mod 15] = gfilog[9] = 10
除法：
    13 / 11 = gfilog[gflog[13] – gflog[11]] =  gfilog[13 – 7] = gfilog[6] = 12

摘自：

https://blog.csdn.net/shelldon/article/details/54729687

https://blog.csdn.net/luotuo44/article/details/41645597