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

1. 模运算

1.1 $Z_n$ 上模运算的三种运算

1. 模加运算：$(a+b) \mod \ n = c$
2. 模减运算：$(a-b) \mod \ n = c$
3. 模乘运算：$(a \times b) \mod \ n = c$

1.2 $Z_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$
• $[(a \mod \ n) \times (b \mod \ n)] \mod \ n = (a \times b) \mod \ n$

1.3 扩展欧几里得求 $Z_n$ 上模运算的乘法逆

/* 扩展欧几里得 */
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(2^n)$

• $GF(2^n)$ 是一个有限域
• 每个元素的加法逆是其本身

AES 中用到了 $GF(2^8)$，对应的不可约多项式及位模式表示为

$$\begin{array}{c} m(x) = x^8 + x^4 + x^3 + x + 1 \end{array}$$

根据长除法可得：

$$\begin{array}{c} x^8 \mod \ m(x) = x^4 + x^3 + x + 1 \\ x^8 \mod \ m(x) = 00011011 \end{array}$$

对于一个多项式

$$\begin{array}{c} f(x) = b_7x^7 + b_6x^6 + b_5x^5 + b_4x^4 + b_3x^3 + b_2x^2 + b_1x + b_0 \end{array}$$

其对应的位模式为

$$\begin{array}{c} f(x) = b_7b_6b_5b_4b_3b_2b_1b_0 \end{array}$$

则 $xf(x)$ 在位模式下表示为：

$$\begin{array}{c} xf(x) = 00000010 \cdot f(x) = \begin{cases} b_6b_5b_4b_3b_2b_1b_00 & if \ b_7 = 0 \\ b_6b_5b_4b_3b_2b_1b_00 \oplus 00011011 & if \ b_7 = 1 \end{cases} \end{array}$$

而对于 $x^2f(x)$、$x^3f(x)$、$\cdots$、$x^7f(x)$ 可以通过递归相乘实现：

$$\begin{array}{c} x^2f(x) = x(xf(x)) \\ x^3f(x) = x(x^2f(x)) \\ \vdots \\ x^7f(x) = x(x^6f(x)) \end{array}$$

由此，可以通过将 $f(x) \cdot 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(2^n)$ 上的加法 XOR ）。