Finite fields - 有限域

有限域（Finite fields）是代数的一个分支，在加密算法、数据压缩算法和纠错算法中都有重要的作用。

概念

域 - field

如果集合F的所有元素与定义在其上的二元操作符+和·满足下面条件，即构成一个域：

  • 闭包（Closure）： 对于任意F中的元素x和y，x+y和x·y也都是F中的元素
  • 结合律（Associative)：对于F中的任意x，y和z，满足(x+y)+z = x+(y+z)和(x·y)·z = x·(y·z)
  • 交换律（Commutative）：对于F中的任意元素x和y，满足x+y = y+x和x·y = y·x
  • 分配率（Distributive）：对于F中的任意元素x，y和z，满足x·(y+z) = (x·y)+(x·z)
  • Identity：F中存在加法单位元，记作0，对F中的任意元素x满足x+0 = x；存在乘法单位元，记作1，对F中的任意元素x满足x·1 = x
  • Inverse：对F中的任意元素x，在F中都能找到对应的y满足x+y = 0，即y = -x，x与y互为负元；对于F中除0外的任意元素x，在F中都能找到对应的y满足x·y = 1，即y = 1/x，x与y互为逆元

比如，实数集R与定义在其上的加法和乘法运算，就构成了一个域。

但是整数集Z不是一个域，因为Z中的非零元素并不都有乘法逆元，比如1/2不在Z中。

虽然Z不是一个域，但是整数模上任意一个素数的集合可以构成一个域。比如mod 5的集合是{0, 1, 2, 3, 4}，记为Z/5，对应的+运算为(x+y)%5，·为(x·y)%5，这时候加法单位元是0，乘法单位元是1，可以发现，(2*3)%5 = 1，所以2的乘法逆元为3

对于任意一个素数p，Z/p是一个域，+运算为(x+y) % p，·运算为(x·y) %p

有限域 - finite field

如果一个域的元素个数是有限的，那么这个域称为有限域。

作为一个程序员，我们接触到最多的有限域是Z/2，只包含0和1两个元素。+运算即为XOR，而·运算为AND。

多项式

早在19世纪初期，数学家最开始提出域的概念就是为了构造多项式。

我们引入一个符合变量x，那么所有使用域F内的元素作为系数与x构成的多项式的集合，记为F[x]。

例如，如果我们使用R作为构造多项式的域，那么x^2+1、x+2、3.14x^2-2.72x+1.41等都属于R[x]。同整数一样，多项式也可以有加法和乘法运算，但不总是有除法运算，比如无法得出(x^2+1)/(x+2)的结果，因此R[x]并不是一个域，因为1/(x+2)可以看成是(x+2)的逆元，但是并不属于R[x]中。

然而，正如整数模上任意一个素数构成的集合可以构成一个域，多项式模上一个素多项式构成的集合可以构成域

素多项式（prime polynomial）：系数为整数并且不能被因式分解成低阶多项式。比如上面的x^2+1，在实数范围内不可被因式分解。因此，R[x]/(x^2+1)就是一个域，这个域中的多项式中x的最高次幂最大只能是1

对于域Z/p，mod一个n次素多项式f(x)的结果为一个具有p^n个元素的域(Z/p)[x]/f(x)。关于f(x)这个素多项式的选择并不重要，因为任意两个大小为p^n的有限域具有相同的结构，将大小为p^n的有限域记为GF(p^n)。

对于多项式，例如x^8+x^4+x^3+x+1，我们可以看作是一个向量[1,0,0,0,1,1,0,1,1]。

GF(2^n)

作为程序员，对我们来说最有趣的是GF(2^n)，即Z/2的多项式扩展，因为GF(2^n)的元素为长度为n的位向量。

例如，(Z/2)[x]/(x^8+x^4+x^3+x+1)，这个域共有2^8个元素，每一个元素为一个长度为8的位向量，代表一个单字节：一个字节的二进制形式 b~7~b~6~b~5~b~4~b~3~b~2~b~1~b~0~ 代表多项式 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~。

加法操作

多项式的加法操作，即把相同次数的项系数相加，因为系数是Z/2的元素，因此系数相加意味着XOR操作

1
(x^2 + x) + (x + 1) = x^2 + 2x + 1 = x^2 + 1

换成二进制形式：110~2~+011~2~=101~2~

乘法操作

多项式的乘法操作比较复杂，需要基于加法的XOR操作

1
(x^2 + x) · (x + 1) = x^3 + x^2 + x^2 + x = x^3 + x

换成二进制形式，具体的计算过程如下：

1
2
3
4
5
6
7
8
     110
 x   011
---------
     110
    110
 + 000
---------
   01010

计算后的结果可能溢出，需要模上对应的素多项式，比如 (Z/2)[x]/(x^8^+x^4^+x^3^+x+1)这个域内的元素的乘法，最后的结果需要模上素多项式式x^8^+x^4^+x^3^+x+1。

我们可以看到，上面的乘法过程中，需要分别执行n次乘法和加法，这个n为具体位向量的长度。而在实际实现域的乘法时，我们会使用查找表来进行优化。这里的查找表不是说建立例如九九乘法表那样的表格，在介绍具体的优化原理之前，需要先介绍一下生成元的概念。

在一个有限域中，至少存在一个元素α，使得域内任意一个非零元素都可以表示为该元素的方幂。

假设一个有限域的非零元素个素为n，并且一个生成元为α，那么 α^n^ = 1。

例如，2是 Z/5 的一个生成元，{α, α^2^, α^3^, α^4^} = {2, 4, 3, 1}。对于GF(p^n)计算会更复杂，但是同样生效。

通过生成元α，域中的任意非零元素都可以表示为α的方幂，我们就可以将元素的乘法转换为幂的加法。因此，我们在实现乘法时，可以先生成一张exp表和一张log表，其中 exp[i] = α^i^， 而 log[α^i^] = i。通过这两张查找表，针对非零元素a和b的乘法可以转换为：a·b = exp[log[a] + log[b]]，只需要执行1次加法和3次查表操作即可。

Code

因为GF(2^8)中一个元素就是一个长度为8的位向量，正好是一个字节大小，因此GF(2^8)在计算机科学中使用最广泛。现在来实现一下GF(2^8)的运算。

首先定义一个域，包含用来优化乘法运算的exp表和log表和素多项式：

1
2
3
4
5
type Field struct {
	poly int
	exp  [255]byte
	log  [256]byte // log[0] is unused
}

构造函数的实现，需要传入一个素多项式和生成元，x^8+x^4+x^3+x+1是GF(2^8)最广泛使用的素多项式，对于的二进制为100011011，对于十进制为283，3是GF(2^8)的一个生成元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func NewField(poly, a int) *Field {
	var f Field
	x := 1
    // 填充exp和log表
	for i := 0; i < 255; i++ {
		f.exp[i] = byte(x)
		f.log[x] = byte(i)
		x = mul(x, a, poly)
	}
	f.poly = poly
	return &f
}

func mul(x, y, poly int) int {
	z := 0
	for x > 0 {
		if x&1 != 0 {
			z ^= y
		}
		x >>= 1
		y <<= 1
		if y&0x100 != 0 {
			y ^= poly
		}
	}
	return z
}

两个查表方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (f *Field) Exp(e int) byte {
	if e < 0 {
		return 0
	}
	return f.exp[e%255] // e^255 = 1
}

func (f *Field) Log(x byte) int {
	if x == 0 {
		return -1
	}

	return int(f.log[x])
}

优化后的乘法运算就是exp[log[a]+log[b]]：

1
2
3
4
5
6
func (f *Field) Mul(a, b byte) byte {
	if a == 0 || b == 0 {
		return 0
	}
	return f.Exp(f.Log(a) + f.Log(b))
}

加法操作就是异或操作：

1
2
3
func (f *Field) Add(a, b byte) byte {
	return a ^ b
}

求乘法逆元：

1
2
3
4
5
6
func (f *Field) Inv(x byte) byte {
	if x == 0 {
		return 0
	}
	return f.Exp(255 - f.Log(x))
}

参考