Digd0g's Blog

有限域-Galois Fields

发表于 更新于 分类于 ，
本文字数： 3.5k 阅读时长 ≈ 13 分钟
       
-------------已经到底啦！-------------
 

有限域亦称伽罗瓦域（Galois Fields），是伽罗瓦于 18 世纪 30 年代研究代数方程根式求解问题时引出的概念。有限域在密码学、近代编码、计算机理论、组合数学等方面有着广泛的应用

设 f(x)，g(x)为有限域 F_q 上的多项式。利用 Weil 关于特征和的定理，我们证明了当 q 足够大时，F_q 有元素ξ使 f(ξ),g(ξ)同时为 F_q 的原根.特别，我们得到了某些二元二次方程 f(x,y)=0有原根解。

这是有限域原根的问题，这里我主要讲解一下有限域上的多项式。

群、环、域

如果<F,+,·>是整环，|F|>1，<F-{0},·>是群，则<F,+,·>是域。故有限整环一定是域

简而言之，群只支持一种运算；环支持两种运算（乘法、加法）并拥有分配律；域支持加、减、乘、除。

[域是一个对加法和乘法封闭的集合，其中要求每个元素都有加法逆元，每个非零元素都有乘法逆元]{.label .warning}若域 F 只包含有限个元素，则称为有限域，[有限域中元素的个数称为有限域的阶]{.label .warning}可以证明，==有限域的阶必为素数的幂==
$$
即有限域的阶可表示为 P^n（p 是素数也是有限域的【特征数】，n 是正整数）\有限域通常记为 GF(p^n)表示P^n元的有限域
$$

最常用的域是GF(P)或GF(2^n)。当n=1时，GF(P)为素数域；当p为素数时，才能保证非零实数集R*中的所有元素都有加法和乘法逆元
$$
有限域 GF(p^n) 中的所有元素可以用\lbrace1, x, x^2, ……, x^{n-1}\rbrace的线性组合来表示\即GF(p^n) = \lbrace a^0 + a^1 x + a^2 x^2 + … + a^{n-1} x^{n-1} | a^i ∈ GF(p), i = 0, 1, 2, …, n-1\rbrace。
$$

$$
若将 GF(p) 上的加法单位元记作 0，乘法单位元记作 1；元素 a 的加法逆元记作 -a，非零元素 b 的乘法逆元记作 b^{-1}\则有：a + (-a) = 0 (mod p), b × b^{-1} = 1 (mod p)。\针对 GF(p) 中的元素 a 和非零元素 b\加法是 (a + b) mod p\减法是 (a + (-b)) mod p\乘法是 a × b mod p\除法是 a × b^{-1} mod p\该算法对多项式运算同样成立\因此 GF(p^n) 上的四则运算可以由 GF(p) 上多项式的四则运算导出。
$$

$$
特别地，当 p=2 时，GF(2^n) 中的元素 a^0 + a^1 x + a^2 x^2 + … + a^{n-1} x^{n-1} 可以转化为二进制数 a^{n-1} … a^2, a^1, a^0.\因为计算机中使用的是二进制数，且 1 字节为 8 位，所以在密码学中常常用到有限域 GF(2^8)
$$

有限域上的加法结构

GF(2^n) 上的加法即为 GF(2) 上多项式的加法，具体是将 GF(2) 上多项式的系数分别相加。而对于 GF(2) 上的元素，加法即为异或运算。所以，GF(2n) 上的加法运算即为按位异或运算

GF(2^n) 上的减法即为 GF(2) 上多项式的减法。具体是将 GF(2) 上多项式的系数分别相减。而对于 GF(2) 上的元素，减法即为加法。所以，GF(2^n) 上的减法即为 GF(2^n) 上的加法

多项式加减法实际上就等价于多项式对于二进制串的按位异或运算
$$
(x^2+1)+(x^2+x+1)=x
$$

$$
101_{2}⊕111_{2}=010_{2}
$$

1
2
3
4
5
6
7
8
9
# 不可约多项式 poly = 0b100011011

0x89 + 0x4d = 0xc4
0xaf + 0x3b = 0x94
0x35 + 0xc6 = 0xf3

0x89 - 0x4d = 0xc4
0xaf - 0x3b = 0x94
0x35 - 0xc6 = 0xf3

有限域上的乘法结构

有限域加减就是异或，但乘法要更复杂一点
$$
记q=p^m,F=GF(q),F*=F-\lbrace0\rbrace。\对任意的\alpha\in F^*,构造\alpha的幂\alpha^0=1,\alpha,\alpha^2,…,由乘法封闭性，每个\alpha^i\in F^*.但F^*中的元素有限，幂序列一定存在重复
$$

$$
设\alpha^k=\alpha^{k+t}是首次重复值，则\alpha^t=1，t就是\alpha的阶\delta_{q}(\alpha)，称\alpha为t次单位原根；且\delta_{q}(\alpha)=q-1
$$

普及一下原根，每个素数p均存在模p的原根
$$
设m\in N，(a,m)=1,使得a^d\equiv1modm成立的最小正整数d称为a对模m的指数(阶)，\记为\delta_{m}(\alpha).\若\delta_{m}(\alpha)=\phi(m),称a是模m的原根
$$
例如

m=7,phi(7)=6

a -3 -2 -1 1 2 3
阶 3 6 2 1 3 6

可见-2，3是原根

回到正题，任一有限域的全体非0元素在域的乘法运算下构成循环群，若能找到F *的一个原根，则F *的所有元素都可由原根的幂得到 (Gauss算法求原根)

例如
$$
x^8 mod m(x) = [m(x) – x^8] = x^4 + x^3 +x +1 \qquad A式
$$
对于多项式f(x)
$$
f(x)=b_{7}x^7+b_{6}x^6+b_{5}x^5+b_{4}x^4+b_{3}x^3+b_{2}x^2+b_{1}x+b_{0}\xf(x)=b_{7}x^8+b_{6}x^7+b_{5}x^6+b_{4}x^5+b_{3}x^4+b_{2}x^3+b_{1}x^2+b_{0}xmodm(x)\若b_{7}=0,结果是小于8的多项式，无需取模计算；\若b_{7}=1，代入A式得到：\xf(x)=b_{6}x^7+b_{5}x^6+b_{4}x^5+b_{3}x^4+b_{2}x^3+b_{1}x^2+b_{0}x+(x^4 + x^3 +x +1)
$$

GF(2^n) 上的乘法即为 GF(2) 上多项式的乘法，具体是将 GF(2) 上的两个多项式相乘，但是两个多项式相乘之后的次数可能大于等于 n，因此在计算两个多项式的乘积之后，还需要模一个 GF(2) 上的 n 次不可约多项式，来保证得到的多项式次数小于 n

在具体实现中，模 n 次不可约多项式的操作可以分解到每一次乘 x 的运算中，即乘 x 的运算通过左移一位后再根据条件按位异或给定的不可约多项式对应的 n 位二进制数的后 n-1 位实现。乘 x 的更高次幂可以通过重复使用该方法实现，这样一来，GF(2^n) 上的乘法结果可由多个中间结果相加得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def gf2_mul(a: int, b: int, poly: int) -> int:
     """
    :param a: 被乘数
    :param b: 乘数
    :param poly: 不可约多项式
    :return: 积
    """
    ans = 0
    digit_1 = poly.bit_length() - 1
    while b:
        if b & 1:
            ans = ans ^ a
        a, b = a << 1, b >> 1
        if a >> digit_1:  # 取出 a 的最高位
            a = a ^ poly
    return ans

$$
101_{2}\bigotimes011_{2}=1111_{2}
$$

有限域上的带余除法

GF(2^n) 上的除法指 GF(2) 上多项式的带余除法，具体是将 GF(2) 上的两个多项式相除，得到商和余数

在具体实现中，令 a 为被除数，b 为除数，q 为商，r 为余数，且均为二进制数形式。将 q 的值初始化为 0，当 a 的比特长度大于等于 b 的比特长度时，b 左移 k 位后与 a 长度相等，此时将 q 与 1 左移 k 位后的值相加，将 a 与 b 左移 k 位后的值相减，再判断 a 与 b 的大小；若 a 大于等于 b，则重复以上步骤，直至 a 小于 b，此时 a 的值即为 r

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def gf2_divmod(a: int, b: int, poly: int) -> (int, int):
    """
    :param a: 被除数
    :param b: 除数
    :param poly: 不可约多项式
    :return: 商，余数
    """
    if b == 0:  # 除数不能为 0
        raise ZeroDivisionError
    ans = 0
    digit_a, digit_b = a.bit_length(), b.bit_length()
    while not a < b:
        rec = digit_a - digit_b
        a = a ^ (b << rec)
        ans = ans | (1 << rec)
        digit_a = a.bit_length()
    return ans, a
'''
# 不可约多项式 poly = 0b100011011

0xde / 0xc6 = 0x01 ... 0x18
0x8c / 0x0a = 0x14 ... 0x04
0x3e / 0xa4 = 0x00 ... 0x3e
'''

其实取模运算就相当于除法啦。多项式取模有一个简单的算法，重复用既约多项式剪掉最高次项。下面是一个极其简单的例子
$$
(x^3+x^2+x+1)mod(x^3+x+1)=x^2
$$

$$
1111_{2}mod1011_{2}=1111_{2}⊕1011_{2}=100_{2}
$$

有限域多项式

$$
GF(2^8)这是GF(p^n)的特例，p=2，n=8。例如多项式:f(x)=x^6+x^4+x^2+x+1，
$$

  1. 多项式的系数只能是0或1（即【0，p-1】）。若p=3，那么系数是可以取0，1，2的；
  2. 合并同类项加法即⊕，对系数进行异或操作
  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
$$

有限域的元素可以通过该域上的本原多项式生成。通过本原多项式得到的域，其加法单位元都是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个之中的某一个。
$$
设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。

不可约多项式

所谓不可约多项式，是指各个系数模质数p的条件下
$$
对于多项式 f(x)，如果不存在两个比此多项式阶小的多项式 f_{1}(x),f_{2}(x),使得f(x)=f_{1}(x)f_{2}(x),就称这个多项式是不可约的。
$$

下面看个例子吧

设置模数为2，多项式为3阶，满足条件的多项式有8个[公式]

这些多项式中，哪些是不可约多项式呢？很明显

[公式]

这4个多项式不满足条件，因为它们都有约数x

$$
x^3+1不满足条件，因为x^3+1=(x+1)(x^2+x+1)
$$

$$
x^3+x^2+x+1不满足条件，x^3+x^2+x+1=(x+1)(x^2+1)
$$

$$
其它2个多项式x^3+x+1,x^3+x^2+1就是不可约多项式了。
$$
找到不可约多项式有什么用呢？我们把不可约多项式设置成“模数”，把各个系数看成集合中的“元素”，把运算⊙定义成多项式乘法，我们就得到了一个群

举个例子，令
$$
f(x)=x^3+x+1，令群包含的元素为{001,010,011,100,101,110,111}，这7个元素实际上分别代表7个多项式
$$

$$
1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1\我们知道，多项式乘法仍然满足交换律，单位元还是设置成1，同时有多项式1的逆元为1；多项式x的逆元为x^2+1
$$
[公式]
$$
多项式x+1的逆元为x^2+x
$$
[公式]
$$
多项式x^2的逆元为x^2+x+1
$$
[公式]

这样一来，{001,010,011,100,101,110,111}中的每一个元素都能找到逆元。在观察这个集合，一共恰好包含了2^3-1个元素。
$$
因此数学上一般把这个乘法群写为Z_{2}[x]/(x^3+x+1)，或者简写为F_{2}3。模数是一个不可约多项式。
$$

多项式运算和之后的密码学有什么关系？这是许多读者需要思考的问题
$$
定义在Z_{2}=\lbrace0,1\rbrace上的多项式有f(x)=a_{n-1}x^{n-1}+…+a_{1}x+a_0=\sum_{i=0}^n a_ix^i\qquad\forall i\in\lbrace0,1,2,…,n-1\rbrace,a_i\in Z_2
$$

$$
那么多项式可以被n元组 ( a_{n − 1}, . . . , a_1 , a_0 ) 唯一表示，\实际上这个二元组就是01序列，n元组 ( a_{n − 1}, . . . , a_1 , a_0 )就是n比特长度的01序列\比如 f ( x ) = x^6 + x^4 + x^2 + x + 1 其表示的就是01010111。\因此多项式就可以唯一地转换为二进制串，在密码学中字符可以被编号为数字，然后数字用二进制表示就可以转换为一个多项式
$$
其实对于计算机而言就是将人对有限域的认知转换为二进制模式

用途

有限域 GF(2^n) 求逆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def gf2_inverse(a: int, poly: int):
    """
    :param a: GF(2^n) 元素
    :param poly: 不可约多项式
    :return: a^(-1)
    """
    x1, x2 = 1, 0
    b = poly
    while b:
        q, r = gf2_divmod(a, b, poly)
        a, b = b, r
        x1, x2 = x2, x1 ^ gf2_mul(q, x2, poly)
    return x1

有限域 GF(2^n) 快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def gf2_quick_pow_mod(a: int, k: int, poly: int) -> int:
    """
    :return: a^k mod p
    """
    res = 1  # res: 计算结果
    while k:
        if k & 1:  # 如果 n 是奇数
            res = gf2_mul(res, a, poly)
        k = k // 2
        a = gf2_mul(a, a, poly)
    return res
'''
# 样例二
a = 1494462659429290047815067355171411187560751791530
k = 65537
p = 2268838711304724304304396119509416774597723292474
# 结果 a^k mod p
res = 2099538163720891467842744895846522520832379454230

'''

python使用自带的 pow 函数 效率更高

参考：

有限域上的多项式 https://www.ruanx.net/polynomial-rsa/

有限域的结构 https://zhuanlan.zhihu.com/p/416128323