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

## 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$

## 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}$

$\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}$

$\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}$