有限域
定义
\(GF[2^m]\)将有限个整数映射到多项式上，使其对于精心定义的加减乘除运算，在\([1,2^m-1]\)范围内运算封闭，从而构成一个有限域
具体地，定义多项式加、减法为系数异或，乘法为多项式相乘后取模，除法为乘以逆多项式
与正常数域类似，我们这里的逆多项式相当于数的乘法逆元，而要想定义逆元，就需要一个素数
同理，我们要找到一个素多项式\(P(x)\)，使其不能被拆为两个多项式的乘积
常用素多项式为：
\(m=4: P(x)=x^4+x+1\)
\(m=8: P(x)=x^8+x^4+x^3+x^2+1\)
\(m=16: P(x)=x^{16}+x^{12}+x^3+x+1\)
我们在密码学中尝试用\(m=8\)的有限域
映射
\(m=8\)时多项式最高次数为\(7\)
也就是说，不同的非零多项式一共有\(2^8-1\)个，且正好与\([1,2^8-1]\)中的数一一对应
具体地，令\(\alpha\)为\(P(x)=0\)的根，则\(\alpha^8=\alpha^4+\alpha^3+\alpha^2+1\)
我们可以列出\(\alpha^n\)在模\(P(\alpha)\)意义下的多项式表示及其对应的二进制数：
\(\alpha^0=\alpha^0 (00000001)\)
\(\alpha^1=\alpha^1 (00000010)\)
\(\vdots\)
\(\alpha^7=\alpha^7 (10000000)\)
\(\alpha^8=\alpha^4+\alpha^3+\alpha^2+1 (00011101)\)
\(\alpha^9=\alpha^5+\alpha^4+\alpha^3+\alpha^1 (00111010)\)
\(\vdots\)
\(\alpha^{11}=\alpha^7+\alpha^6+\alpha^5+\alpha^3 (11101000)\)
\(\alpha^{12}=\alpha^8+\alpha^7+\alpha^6+\alpha^4=\alpha^7+\alpha^6+(\alpha^4+\alpha^4)+\alpha^3+\alpha^2+1=\alpha^7+\alpha^6+\alpha^3+\alpha^2+1 (11001101)\)
\(\vdots\)
剩余的不具体列出
事实上，这里的\(\alpha\)是\(GF[2^m]\)的一个生成元，由它生成的多项式与\([1,2^m-1]\)的整数一一对应，形成双射关系
可以看出我们找出的素多项式的一个性质为：从生成元\(\alpha\)开始生成域中元素，产生循环的大小正好为\(2^m-1\)
事实上上面的列表中，\(\alpha^{255}=\alpha^0=1\)，环的大小为从\(\alpha^0\)到\(\alpha^{254}\)，一共\(255\)个元素；同时这也说明了,一个生成元素\(\alpha^n\)，如果指数\(n\geq255\),那么将从\(0\)开始重新循环，这就说明任意两个生成元素相乘，结果一定还在范围内，即生成元素乘法封闭，这保证了域中实际的数乘也是封闭的
运算
加法
对于加法，我们将两个整数对应的多项式拿出来进行前面所说的多项式异或，其实就是二进制数直接异或
可以看出最高次数为\(7\)的多项式相加后仍然满足在域中，我们有加减法封闭
code:
int add(int a,int b){
return a^b;
}
int sub(int a,int b){
return add(a,b);
}
乘法
首先说明一下乘法的封闭性
我们这样定义乘法运算，使得二进制数的乘法变成相对应的多项式的取模乘法，而多项式取模乘法又对应着生成元相乘。 由于生成元相乘中，指数相加\(\mod 255\)是在\([0,254]\)上封闭的，所以生成元的乘法是在\([\alpha^0,\alpha^{254}]\)上封闭的，那么相对应的二进制数乘法也封闭
那么给出朴素的乘法，采用快速幂相似的写法，把乘方操作改为乘二，这样就变为了普通乘法
同时，在被乘数变大的同时，对他取模，就可以得到最终结果
unsigned char mul(char a1,unsigned char a2){
unsigned char v5 = 0;
while ( a1 && a2 )
{
if ( (a2 & 1) != 0 ) v5 ^= a1;
if (a1 >= 0) a1 *= 2;
else
a1 = (2 * a1) ^ 0x1D;
a2 >>= 1;
}
return v5;
}
进一步，我们将两个整数对应的多项式拿出来，这两个多项式是\(\alpha^n\)和\(\alpha^m\)在模\(P(\alpha)\)意义下的多项式表示，所以两者相乘取模后对应的多项式即为\(\alpha^{(n+m)\mod 255}\)在模\(P(\alpha)\)意义下的多项式表示
这样，我们就可以像上面列表一样，打出一个映射表来：
table[0] = 1;//a^0
for(int i = 1; i < 255; ++i){
if(table[i-1] & 0x80 ){
table[i] = (table[i-1] << 1) ^ 0x1D;
}else{
table[i] = (table[i-1] << 1);
}
}
这样就将两个数的乘法转换为了\(\alpha^n\)和\(\alpha^m\)指数相加，然后查表中对应\(\alpha^{(n+m)\mod 255}\)的二进制数，则这个数就是结果
前面这个表是生成元映射到二进制数的正表
为了反查表，我们还需要一个反表，把二进制数映射到生成元
for(int i = 0; i < 255; ++i) arc_table[table[i]] = i;
最后的乘法：
unsigned char mul(unsigned char x, unsigned char y){
if( !x || !y ) return 0;
return table[ (arc_table[x] + arc_table[y]) % 255];
}
除法
在\(P(x)\)的模意义下，逆多项式得以存在，所以我们有逆元表：
for(int i = 1; i < 256; ++i){
int k = arc_table[i];
k = 255 - k;
k %= 255;
inverse_table[i] = table[k];
}
这样得到的表满足
mul(i,inverse_table[i])=1
这样就有除法：
unsigned char div(unsigned char x,unsigned char y){
return mul(x, inverse_table[y]);
}
例
给出几个乘法例子：
\(8\times 4=32\)
在表中\(8\)对应着\(\alpha^3\),\(4\)对应着\(\alpha^{2}\),乘出来的\(\alpha^5\)对应的二进制数即为\(32\)
这和普通乘法长得很像
\(3\times 7=9\)
在表中\(3\)对应着\(\alpha^{25}\),\(7\)对应着\(\alpha^{198}\),乘出来的\(\alpha^{223}\)对应的二进制数即为\(9\)
事实上，二进制数\(3\)和\(7\)对应的多项式\(\alpha^1+1\)和\(\alpha^2+\alpha^1+1\)直接相乘后取模，结果为\(\alpha^3+1\), 即为\(9\)
\(142\times 71=173\)
在表中\(142\)对应着\(\alpha^{254}\),\(71\)对应着\(\alpha^{253}\),乘出来的\(\alpha^{252}\)对应的二进制数即为\(173\)