群环域以及域上的多项式操作

1. 模运算

1.1 ZnZ_nZn​ 上模运算的三种运算

1. 模加运算：(a+b) mod n=c
2. 模减运算：(a−b) mod n=c
3. 模乘运算：(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​ 上模运算的乘法逆

/* 扩展欧几里得 */
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

• 乘运算：等价于逻辑于 AND

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 ）。