1. 模运算
1.1 ZnZ_nZn 上模运算的三种运算
- 模加运算：(a b) mod n=c
- 模减运算：(a−b) mod n=c
- 模乘运算：(a×b) mod n=c
1.2 ZnZ_nZn 上三种运算的性质
- [(a mod n) (b mod n)] mod n=(a b) mod n
- [(a mod n)−(b mod n)] mod n=(a−b) mod n
- [(a mod n)×(b mod n)] mod n=(a×b) mod n
1.3 扩展欧几里得求 ZnZ_nZn 上模运算的乘法逆
代码语言：javascript复制/* 扩展欧几里得 */
int exgcd(int a, int b, int & x, int & y)
{
int ans = 0;
if(b == 0) {
x = 1;
y = 0;
ans = a;
} else {
ans = exgcd(b,a%b,x,y);
int t = x;
x = y;
y = t - (a/b)*y;
}
return ans;
}2. 群环域
3. 伽罗瓦域
3.1 GF(2)
- 加/减运算：等价于逻辑异或 XOR
0 0 = 0 | 0 – 0 = 0 |
|---|---|
0 1 = 1 | 1 – 0 = 1 |
1 0 = 1 | 0 – 1 = 0 1 = 1 |
1 1 = 0 | 1 – 1 = 1 1 = 0 |
- 乘运算：等价于逻辑于 AND
0 ×times× 0 = 0 |
|---|
0 ×times× 1 = 0 |
1 ×times× 0 = 0 |
1 ×times× 1 = 1 |
3.2 GF(2n)
- GF(2n)是一个有限域
- 每个元素的加法逆是其本身
AES 中用到了 GF(2^8)，对应的不可约多项式及位模式表示为
m(x)=x8 x4 x3 x 1
根据长除法可得：
x8 mod m(x)=x4 x3 x 1
x8 mod m(x)=00011011
对于一个多项式
f(x)=b7x7 b6x6 b5x5 b4x4 b3x3 b2x2 b1x b0
其对应的位模式为
f(x)=b7b6b5b4b3b2b1b0
则 xf(x) 在位模式下表示为：
而对于 x2f(x)、x3f(x)、⋯cdots⋯、x7f(x) 可以通过递归相乘实现：
由此，可以通过将 f(x)⋅g(x) 中的多项式 f(x)或 g(x) 中的任意一个（比如这里取 g(x)分解为
begin{array}{c} b_7 cdot 2^7 b_6 cdot 2^6 b_5 cdot 2^5 b_4 cdot 2^4 b_3 cdot 2^3 b_2 cdot 2^2 b_1 cdot 2^1 b_0 cdot 2^0 end{array}
然后利用乘法分配律分别计算每项与 f(x) 相乘，最后再相加（即 GF(2n)上的加法 XOR ）。
