# 【密碼學 II - Basic Number Theory】

## 01. 整數算術 (Integer Arithmetic)

這部分回顧了整數的基本運算，為後續的模數算術打下基礎 。

### 01-01. 整數集合 (Z) 與二元運算
- **整數集合 (Z)**：包含從負無窮大到正無窮大的所有整數 ( ... , -2, -1, 0, 1, 2, ... )。

* **二元運算**：作用於整數集合的運算，可接受兩個輸入值，並產生一個輸出值。
1. 主要有三種：加法、減法、乘法。
2. 例如：`5 + 3 = 8`、`7 - 4 = 3`、`6 * 2 = 12`。

### 01-02. 整數除法 (Integer Division)
* 將整數 `a`（被除數）除以 `n`（除數），會得到商 `q` 和餘數 `r`。
* **關係式**：`a = q * n + r`，其中 `0 ≤ r < n`。
1. `q = floor(a / n)`
2. `r = a mod n` (在密碼學中，餘數 `r` 必須為正)
* **範例**：
1. `a = 25`, `n = 7`
2. `25 = 3 * 7 + 4` ( q = 3, r = 4 )
* **處理負數**：當 `a` 為負數時，電腦計算的 `r` 和 `q` 可能為負。
1. 例如：`-25` 除以 `7`，電腦可能算出 `-25 = (-3) * 7 + (-4)`。
2. **修正規則**：為使 `r` 變為正數，我們將 `q` 值減 1，並將 `r` 值加 `n`。
3. **修正後**：`q = -3 - 1 = -4`、`r = -4 + 7 = 3`
4. **驗證**：`a = (-4) * 7 + 3 = -28 + 3 = -25`。因此正確表示為 `q = -4, r = 3`。

### 01-03. 整除性 (Divisibility)
* 如果 `a = q * n + r` 且 `r = 0`，代表 `n` 可以整除 `a`，記為 $n \mid a$。
* 如果 `r ≠ 0`，代表 `n` 無法整除 `a`，記為 $n \nmid a$。
* **範例**：
1. $4 \mid 32$ (因為 $32 = 8 \times 4 + 0$)
2. $8 \nmid 42$ (因為 $42 = 5 \times 8 + 2$)
3. $13 \mid 78$, $7 \mid 98$, $−6 \mid 24$, $4 \mid 44$, $11 \mid (−33)$
* **基本性質**：
1. 如果 $a \mid 1$， 則 $a = \pm 1$。
2. 如果 $a \mid b$ 且 $b \mid a$，則 $a = \pm b$。

### 01-04. 整除性的重要性質
* **性質 1 (遞移性)**：若 $a \mid b$ 且 $b \mid c$，則 $a \mid c$。
* `範例`：$3 \mid 6$ 且 $6 \mid 18$，則 $3 \mid 18$。
* **性質 2 (線性組合)**：若 $a \mid b$ 且 $a \mid c$，則對於任意整數 `m` 和 `n`，恆有 $a \mid (m \times b + n \times c)$。
* `範例`：$5 \mid 10$ 且 $5 \mid 25$。取 $m=2, n=3$，則 $5 \mid (2 \times 10 + 3 \times 25)$ $\Rightarrow$ $5 \mid (20 + 75)$ $\Rightarrow$ $5 \mid 95$。
* **性質 3 (因數)**：整數 1 只有一個正因數 (Divisor)，就是 1。
* **性質 4 (因數)**：任何大於 1 的整數至少有 2 個正因數，1 和它自己。

### 01-05. 最大公因數 (Greatest Common Divisor, GCD)
`gcd(a, b)` 是指所有能同時整除 `a` 和 `b` 的最大正整數。
- `範例`：`gcd(12, 18) = 6`。
- `範例`：`gcd(25, 60) = 5`。

**歐幾里德演算法 (Euclidean Algorithm)**：一種用來求 GCD 的高效方法，基於 $gcd(a, b) = gcd(b, r)$ 的原理，其中 $r$ 是 $a$ 除以 $b$ 的餘數 。
- 一種用來求 GCD 的高效方法，基於 $gcd(a, b) = gcd(b, r)$ 的原理，其中 $r = a \mod b$。
- `範例：試求 gcd(2740, 1760)`


### 01-06. 歐幾里德延伸演算法 (Extended Euclidean Algorithm)
* 除了找出 `d = gcd(a, b)`，還能找出整數 `s` 和 `t`，使其滿足貝祖等式 (Bézout's identity)：$s \times a + t \times b = gcd(a, b)$
* 這個演算法在後續求乘法反元素時非常重要。
* **互質 (Relatively Prime)**：當 $gcd(a, b) = 1$ 時，我們說 `a` 和 `b` 互質。

:::success
- 給定 $a = 161$ 和 $b = 28$，求出 $gcd(a, b)$ 以及 $s$ 和 $t$ 的值？$gcd(161, 28) = 7$，$s = −1$ 和 $t = 6$
- 給定 $a = 17$ 和 $b = 0$，求出 $gcd(a, b)$ 以及 $s$ 和 $t$ 的值？$gcd(a, b) = s * a = 17$, $s = 1$, $t = 0$
- 給定 $a = 0$ 和 $b = 45$，求出 $gcd(a, b)$ 以及 $s$ 和 $t$ 的值？$gcd(a, b) = s * a = 45$, $s = 0$, $t = 1$
:::

### 01-07. 線性 Diophantine 方程式 (Linear Diophantine Equation)
* 形式為 `ax + by = c` 的線性不定方程式，求解整數解 `x` 和 `y`。
* **解的條件**：令 `d = gcd(a, b)`。只有當 `d|c`（`d` 能整除 `c`）時，此方程式才有整數解。
* **特解 (Particular Solution)**：
1. 利用延伸歐幾里德演算法求出 `s`, `t` 使得 `as + bt = d`。
2. 特解 $x_0 = (c / d) \times s$ 和 $y_0 = (c / d) \times t$。
* **通解 (General Solution)**：
1. $x = x_0 + k \times (b / d)$
2. $y = y_0 - k \times (a / d)$，其中 `k` 為任意整數。

:::success
**重點筆記**：
- 求出方程式 $21x + 14y = 35$ 的特解和通解

- 舉例來說，我們要把 100 美元的支票兌換成一些由 20 美元和 5 美元的鈔票。利用求解線性 Diophantine 方程式 $20x + 5y = 100$，可以找出許多不同的兌換方式。因為 $d = gcd(20, 5) = 5$，而且 $5 \mid 100$，此方程式有無限多解，但本例中，這些解中只有少數是合理的 ( $x$ 值和 $y$ 值必須同時為非負整數解)
1. `d = gcd(20, 5) = 5`。$5 \mid 100$，有解。
2. 此情境只要求 $x, y$ 均為非負整數的解（例如 x=5, y=0 或 x=2, y=12）。
:::
<br>

## 02 模數算術 (Modular Arithmetic)
這是密碼學的核心，主要關注除法運算中的餘數 。

### 02-01. 模運算子 (Modulo Operator)
* 符號為 `mod`，`a mod n` 的結果就是 `a` 除以 `n` 的餘數 `r`。
* `範例`：
1. `27 mod 5 = 2` (因為 $27 = 5 \times 5 + 2$)
2. `10 mod 2 = 0` (因為 $10 = 5 \times 2 + 0$)

### 02-02. 餘數集合 (Set of Residues, Zn)
* `Zn` 是由模 `n` 運算後所有可能的餘數所組成的集合。
* `Zn = {0, 1, 2, ..., n-1}`。
* `範例`：
1. $Z_2 = \{0, 1\}$
2. $Z_5 = \{0, 1, 2, 3, 4\}$
3. $Z_{10} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$

### 02-03. 同餘 (Congruence)

* 如果兩個整數 `a` 和 `b` 在除以 `n` 後有相同的餘數，則稱 `a` 和 `b` 在模 `n` 之下同餘。
* 記為 $a \equiv b \pmod n$。
* `範例`：
1. $27 \equiv 12 \pmod 5$
2. `說明`：因為 $27 \mod 5 = 2$，且 $12 \mod 5 = 2$，兩者餘數相同。
3. `同理`：$100 \equiv 2 \pmod 7$ ( $100 = 14 \times 7 + 2$ )

### 02-04. Zn 下的運算與性質
* 在 `Zn` 集合中也可以進行加、減、乘運算，其結果都需要再做一次 `mod n` 來確保仍在 `Zn` 集合內。
* 範例 (在 $Z_8$ 中)：
1. `加法`：$(5 + 7) \mod 8 = 12 \mod 8 = 4$
2. `減法`：$(3 - 6) \mod 8 = -3 \mod 8 = 5$
3. `乘法`：$(5 \times 3) \mod 8 = 15 \mod 8 = 7$
* **重要性質**：
1. `(a + b) mod n = [(a mod n) + (b mod n)] mod n`
2. `(a - b) mod n = [(a mod n) - (b mod n)] mod n`
3. `(a * b) mod n = [(a mod n) * (b mod n)] mod n`
* `範例`：計算 $(1234 \times 5678) \mod 10$
1. $1234 \mod 10 = 4$
2. $5678 \mod 10 = 8$
3. $(4 \times 8) \mod 10 = 32 \mod 10 = 2$
4. (這比計算 $1234 \times 5678 = 7006652$ 再取 mod 10 要快)

### 02-05. 反元素 (Inverse)
**加法反元素 (Additive Inverse)**：
* 在 `Zn` 中，若 $a + b \equiv 0 \pmod n$，則 `a` 和 `b` 互為加法反元素。
* 在 `Zn` 中，每個整數 `a` 都有加法反元素，即 `(n - a)`。
* 範例 (在 $Z_9$ 中)：
1. `3` 的加法反元素是 `6`，因為 $(3 + 6) \mod 9 = 0$。
2. `5` 的加法反元素是 `4`，因為 $(5 + 4) \mod 9 = 0$。

**乘法反元素 (Multiplicative Inverse)**：
* 在 `Zn` 中，若 $a \times b \equiv 1 \pmod n$，則 `b` 稱為 `a` 的乘法反元素，記為 $a^{-1}$。
* **存在條件**：並非每個整數都有乘法反元素。只有當 $gcd(a, n) = 1$（a 和 n 互質）時，`a` 在 `Zn` 中才存在乘法反元素。
* **求解**：可以使用歐幾里德延伸演算法來求解。
* 範例 (在 $Z_7$ 中求 3 的反元素)：
1. 我們在找 $3x \equiv 1 \pmod 7$。
2. `1. 檢查`：$gcd(3, 7) = 1$，所以存在反元素。
3. `2. 求解`：$3 \times 5 = 15 \equiv 1 \pmod 7$。
4. `結果`：$3$ 在 $Z_7$ 中的乘法反元素是 $5$。
* 範例 (在 $Z_8$ 中求 4 的反元素)：
1. `1. 檢查`：$gcd(4, 8) = 4$。
2. `結果`：因為 $gcd \neq 1$，所以 $4$ 在 $Z_8$ 中沒有乘法反元素。

<br>

## 03 矩陣 (Matrix)
矩陣在密碼學中也常被使用，這裡回顧了其基本運算 。
- **基本運算**：包含矩陣的加法、減法、乘法以及純量乘法 。
- **行列式 (Determinant)**：只有方陣才有行列式，是一個純量值 。
- **反矩陣 (Inverse Matrix)**：只有方陣可能存在反矩陣。若矩陣 `A` 的反矩陣為 `A⁻¹`，則 `A * A⁻¹ = A⁻¹ * A = I` (單位矩陣) 。
- **餘數矩陣 (Residual Matrix)**：矩陣中的所有元素都定義在 Zn 中 。一個餘數矩陣 A 具有乘法反矩陣的條件是 `gcd(det(A), n) = 1` 。

<br>

## 04 線性同餘 (Linear Congruence)
這部分討論如何解在 `Zn` 中的線性方程式 。
- **單變數線性方程式**：形式為 `ax ≡ b (mod n)`。
- **解的條件**：令 `d = gcd(a, n)`。
1. 如果 `d` 無法整除 `b (dłb)`，則方程式無解 。
2. 如果 `d` 可以整除 `b (d|b)`，則方程式恰好有 `d` 個解 。