一、伽罗瓦域

如果m等于一个素数p的n次幂（n为正整数），即：m = p^n时，才存在一个m阶的域。

n等于1时,叫做素域(Prime Field)
n >= 2时，叫做扩展域(Field Extension)
这两种情况加法单位元都为0，乘法单位元1.

都是循环群
素域的运算为模加，模乘
扩展域的运算为模加、素多项式基础上的多项式运算

1、为何必须是这种形式？

同樣大小的兩個有限域一定是同構的。

当m=p为素数时，才能保证集合中的所有的元素都有乘法逆元(0除外)。即对于域中的任一个元素a，总能在域中找到另外一个元素b，使得a*b mod p 等于1。

m = p^n时,使用多项式运算来保证域的条件

因為域與域之間的函數一定是單射，所以F_p一定是嵌在F_p^r裡的，於是他張開了一個線性空間。
$GF(2^8)$如果是F_2上一個域的話，就可以很簡單看成一個八次元的向量，每個坐標都是0或1。

2、$G(2^n)$

G(2),加减法 xor、 乘法 and
$G(2^n)$,加减法 xor 、 乘法 扩展欧几里得算法(利用生成元乘除)

二、扩展域

1、用多项式表达的扩展域

对于$GF(2^8)$来说，我们并不能直接用0-255这256个数字来表示了，取而代之的方法，是使用多项式。$GF(2^8)$中的每一个元素，都用形如：
$a_7x^7 + a_6x^6 + a_5x^5 + ... + a_1x + a_0$
这样的多项式表达。其中，$a_0 - a_7$是多项式的系数，它们只能从GF(2)中取值。这样，$a_0 - a_7$ 就代表了一个字节中的对应bit。并且，这些系数的运算法则，也使用刚才GF(2)中提到的加法和乘法法则。来看个例子：下面这两个，都是$GF(2^8)$中的元素：
$A(x) = x^7 + x^5 + x^3 + 1$
$B(x) = x^2 + 1$

2、多项式加法

按照之前的约定，它们分别表示二进制数的10101001和00000101。接下来，为了在$GF(2^8)$中计算A(x) + B(x)，我们只要按位依次执行GF(2)中的加法（计算机中的xor）就好了，也就是说它等于：

  1 0 1 0 1 0 0 1
+ 0 0 0 0 0 1 0 1
------------------
  1 0 1 0 1 1 0 0

把这个结果对应到多项式，就是$x^7 + x^5 + x^3 + x^2$而这个多项式对应的字节，是0xab。

3、多项式减法等于加法，因为逆元就是自己

无所谓的减法(减法就等于加法)，或者负系数。所以，$x^4 - x^4$就等于$x^4 + x^4$。$-x^3$就是$x^3$。

4、多项式乘法

但$GF(2^8)$多项式的乘法，就麻烦一些了。为了计算A(x)B(x)，我们先按照普通代数的计算方法展开多项式：
$A(x)B(x) = (x^7 + x^5 + x^3 + 1)(x^2 + 1)$
$\quad = x^9 + x^7 + x^5 + x^2 + x^7 + x^5 + x^3 + 1$
$\quad = x^9 + 2x^7 + 2x^5 + x^3 + x^2 + 1$
然后，把这个多项式的系数对2取模：

    x^9 + 2x^7 + 2x^5 + x^3 + x^2 + 1
mod 2
--------------------------------------
    x^9                 x^3 + x^2 + 1

这样，就可以得到$x^9 + x^3 + x^2 + 1$。但问题是$x^9$已经超过了$GF(2^8)$可以表达的范围，它也对应不到计算机的一个字节中的bit。显然这个结果是不对的，怎么办呢？
其实，思路和刚才在处理GF(2)加法结果的时候是类似的。既然我们要把结果限定在$x^8$以内，那就把多项式对$x^8$取模不就行了。道理是这么个道理，不过这个取模的多项式，可不是随便选的。
AES的设计者Vincent Rijmen 使用了一个经典的不可约多项式：$P(x) = x^8 + x^4 + x^3 + x + 1$。
什么是不可约呢？就是说，$P(x)$不能表示为$GF(2^8)$域中两个多项式的乘积。这和自然数中的素数是类似的，因此，$P(x)$也叫素多项式。
由于P(x)的最高次幂是8，因此对P(x)取模，结果就一定会落在$GF(2^8)$里了，我们来算一下。先算$xP(x)$让P(x)升到9次幂：
$xP(x) = x^9 + x^5 + x^4 + x^2 + x$
其次，用$x^9 + x^3 + x^2 + 1 - x(Px)$

  x^9 +             x^3 + x^2     + 1
- x^9 + x^5 + x^4 +       x^2 + x
--------------------------------------
        x^5 + x^4 + x^3       + x + 1

这样，得到的结果就落在$GF(2^8)$里了，它表示的二进制数是00111011，这就是$GF(2^8)$中$A(x)B(x)$的运算结果。
这个过程，数学上使用多项式长除法，形如：


简化计算的方法，避免长除法，如下，因为：
$x^8\ (mod\ P(x)) = P(x) -x^8 = x^4+ x^3 +x^2 + x1$
将高次多项式的$x^8$替换为$x^4 + x^3 + x^2 +1$而不用进行除法取模计算
虽然可以通过替换减少除法计算，但还是过于复杂。因此通过生成元查表来计算。

int table[256];
int i;

table[0] = 1;//g^0
for(i = 1; i < 255; ++i)//生成元为x + 1
{
    //下面是m_table[i] = m_table[i-1] * (x + 1)的简写形式
    table[i] = (table[i-1] << 1 ) ^ table[i-1];
 
    //最高指数已经到了8，需要模上m(x)
    if( table[i] & 0x100 )
    {
        table[i] ^= 0x11B;//用到了前面说到的乘法技巧-替换
    }
}

详见下节

5、求多项式的逆元（用于计算乘除法）

在域GF(2^w)中2总是生成元。

了解了多项式乘法之后，我们就能计算$GF(2^8)$中任意一个多项式A(x)的逆元了，AES加密算法需要这个值。要说明的是，选取的素多项式不同，$GF(2^8)$中元素的逆元也不同。这里，我们就用刚才说到的P(x)举例了。
对于给定的一个$GF(2^8)$中的多项式A(x)，如果A(x)B(x)的结果对P(x)取模等于1，那么B(x)就是A(x)的逆元了。那该怎么计算这个B(x)呢？
第一种方法，当然就是暴力穷举。用$GF(2^8)$中的每一个元素分别和A(x)计算；
第二种方法，来自于一个有趣的现象。$GF(2^8)$中的每一个非0多项式，都可以表示成(x+1)的n次幂，这里0<=n<=254，例如：
$(x+1)^0 = 1$
$(x+1)^1 = x+1$
$(x+1)^2 = x^2+1$
...
$(x+1)^{254} = x^7+x^6+x^5+x^4+x^3+x^2+x$
注意这里我们执行的是GF(2)中的加法和乘法。并且，当n从255开始，就又会用和之前同样的顺序遍历$GF(2^8)$中的多项式。
$(x+1)^{255} = 1$
$(x+1)^{256} = x+1$
...
正是由于这种特性，(x+1)有了一个形象的名字，叫做生成元。有了生成元之后，我们可以把$GF(2^8)$中的每一个多项式和它对应的生成元的幂保存成一个映射表。接下来，对于给定的A(x)，如果B(x)是A(x)的逆元，则一定有下面的关系成立：
$A(x)B(x) = (x+1)^a (x+1)^b = (x+1)^(a+b) = 1 (mod\ P(x))$
于是，我们只要根据之前创建的映射表，查到A(x)对应的幂a，然后用255-a计算出b，再从表中查出b对应的多项式，就是A(x)的逆元了。

6、利用生成元，查表计算乘除法

乘除法同理，只要查表获取指数，指数相加减mod255后，反查的原数即可。
常用本原多项式 ：
$GF(2^3) : \ x^3+x+1$
$GF(2^4) : \ x^4+x+1$
$GF(2^8) : \ x^8+x^4+x^3+x^2+1$
$GF(2^{16}) : \ x^{16}+x^{12}+x^3+x+1$
$GF(2^{32}) : \ x^{32}+x^{22}+x^2+x+1$
$GF(2^{64}) : \ x^{64}+x^4+x^3+x+1$

通过本原多项式生成元素
设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^14x=(x^3+1)x=x^4+x=1，生成结束。

注意：多项式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

生成gflog,gfilog的python 代码

# coding=UTF-8
# key : value => w : primitive_polynomial
primitive_polynomial_dict = {4: 0b10011,                            # x**4  + x     + 1
                             8: (1 << 8) + 0b11101,                 # x**8  + x**4  + x**3 + x**2 +1
                             16: (1 << 16) + (1 << 12) + 0b1011,    # x**16 + x**12 + x**3 + x    + 1
                             32: (1 << 32) + (1 << 22) + 0b111,     # x**32 + x**22 + x**2 + x    + 1
                             64: (1 << 64) + 0b11011                # x**64 + x**4  + x**3 + x    + 1
                             }

def make_gf_dict(w):
    gf_element_total_number = 1 << w
    primitive_polynomial = primitive_polynomial_dict[w]

    gfilog = [1]  # g(0) = 1
    for i in xrange(1, gf_element_total_number - 1):
        temp = gfilog[i - 1] << 1  # g(i) = g(i-1) * g
        if temp & gf_element_total_number:  # if overflow, then mod primitive polynomial
            temp ^= primitive_polynomial  # mod primitive_polynomial in GF(2**w) == XOR
        gfilog.append(temp)
 
    assert (gfilog[gf_element_total_number - 2] << 1) ^ primitive_polynomial
    gfilog.append(None)
 
    gflog = [None] * gf_element_total_number
    for i in xrange(0, gf_element_total_number - 1):
        gflog[gfilog[i]] = i
 
    print "{:>8}\t{:>8}\t{:>8}".format("i", "gfilog[i]", "gflog[i]")
    for i in xrange(0, gf_element_total_number):
        print "{:>8}\t{:>8}\t{:>8}".format(i, gfilog[i], gflog[i])

if __name__ == "__main__":
   make_gf_dict(4)

来源参考：
https://boxueio.com/series/let-us-build-an-apn-provider/ebook/562
https://blog.csdn.net/shelldon/article/details/54729687

• 小说散文全部石油视频
• 小说散文答题模板II
• 对比法元智能
• 误差传播：计算多个测量误差的合成不确定度
• 2020 年全国高考 1 卷第 20 题

发表新评论 取消回复

发送