# 【密碼學 IX - Prime & Congruence Equations】
## 01. 質數基礎 (Primes)
### 01-01. 定義與分佈
正整數可以依據因數數量分為三類：
1. **數值 1**：只有一個因數。
2. **質數 (Primes)**：大於 1，且因數只有 1 和自己（例如：2, 3, 5, 7...）。
3. **合成數 (Composites)**：大於 1，且有兩個以上的因數。
:::success
**重點筆記**：最小的質數
最小的質數是 **2**，因為它只能被 2（自己）和 1 整除。
:::
:::success
**重點筆記**：小於 10 的質數有四個：2、3、5、7。
**觀察**：在 1 到 10 的範圍中，質數佔比為 40%。但隨著範圍擴大，質數的密度會逐漸下降。
:::
**質數的個數與分佈：**
* **無限多個**：質數有無限多個。
* **$\pi(n)$ 函數**：表示小於或等於實數 $n$ 的質數個數。
* **分佈範圍**：根據 Gaussian 與 Legendre 的猜想，其漸近函數滿足：
$$\frac{n}{\ln n} < \pi(n) < \frac{n}{\ln n - 1}$$
:::success
**重點筆記**：質數無限性的構造證明
- 假設只存在有限個質數集合 $\{2, 3, 5, 7, 11, 13, 17\}$。
- 令 $P = 2 \times 3 \times \dots \times 17 = 510510$。
- 考慮 $P + 1 = 510511$。經計算發現 $510511 = 19 \times 97 \times 277$。
- 這些因數（19, 97, 277）都不在原本的集合中，證明大於 17 的質數必定存在。
:::
:::success
**重點筆記**：估算質數個數
- 求小於 1,000,000 的質數個數。
- 利用近似公式計算範圍約為 72,383 到 78,543。
- 實際個數為 **78,498**。
:::
**基本的質數檢查（試除法）：**
要判斷 $n$ 是否為質數，需測試所有小於 $\sqrt{n}$ 的質數是否能整除 $n$。
:::success
**重點筆記**：質數判定
- **97 是否為質數？** $\lfloor\sqrt{97}\rfloor = 9$。檢查質數 $\{2, 3, 5, 7\}$。皆無法整除，故 **97 是質數**。
- **301 是否為質數？** $\lfloor\sqrt{301}\rfloor = 17$。檢查質數 $\{2, 3, 5, \dots, 17\}$。發現 $301 \div 7 = 43$，整除，故 **301 不是質數**。
:::
### 01-02. 尤拉 $\phi$ 函數 (Euler's Phi-Function)
$\phi(n)$ 表示小於等於 $n$ 且與 $n$ 互質的正整數個數。此函數在 RSA 密碼學中至關重要。求出 $\phi(n)$ 的難度等同於對 $n$ 進行因數分解。
**計算規則一**：$\phi(1) = 1$。
**計算規則二**：若 $p$ 為質數，$\phi(p) = p - 1$。
:::success
**重點筆記**：$\phi(13) = 13 - 1 = 12$。
:::
**計算規則三**：若 $m, n$ 互質，**$\phi(m \times n) = \phi(m) \times \phi(n)$**。
:::info
注意事項：證明的核心邏輯：利用「中國餘數定理 (CRT)」，將檢查一個大數的問題，拆解成檢查兩個小數的問題。
1. 互質的條件可以拆開來看要判斷一個數字 $x$ 是否跟大數 $mn$ 互質，其實只需要檢查：$x$ 是否跟 $m$ 互質？且 $x$ 是否跟 $n$ 互質？如果兩者皆是，那 $x$ 就一定跟 $mn$ 互質。
2. 每個數字都有唯一的「座標」根據中國餘數定理，每一個在 $1$ 到 $mn$ 之間的數字 $x$，都可以唯一對應到一組餘數座標 $(p, q)$：$p = x \pmod m$$q = x \pmod n$這就像是每個 $x$ 都有一個獨一無二的身分證號碼 $(p, q)$。
3. 算出有多少種合法的組合我們要找的是「與 $mn$ 互質的 $x$ 有幾個」，也就是 $\phi(mn)$。這等同於在找有多少組座標 $(p, q)$ 滿足互質條件：對於 $p$ (座標左邊)：它必須與 $m$ 互質。在 $1$ 到 $m$ 之間，這樣的數有 $\phi(m)$ 個。對於 $q$ (座標右邊)：它必須與 $n$ 互質。在 $1$ 到 $n$ 之間，這樣的數有 $\phi(n)$ 個。
4. 結論根據排列組合的乘法原理，合法的座標組合總數就是：$$\text{左邊的選擇數} \times \text{右邊的選擇數} = \phi(m) \times \phi(n)$$因為座標組合數等於 $x$ 的數量，所以證明了 $\phi(mn) = \phi(m)\phi(n)$。
:::
:::success
**重點筆記**：計算 $Z_{14}^*$ 的元素個數。
- $\phi(14) = \phi(2) \times \phi(7) = 1 \times 6 = 6$。
- 元素為 $\{1, 3, 5, 9, 11, 13\}$。
- **註：若 $n > 2$，$\phi(n)$ 必為偶數。**
:::
**計算規則四**：若 $p$ 為質數，$e$ 為正整數，**$\phi(p^e) = p^e - p^{e-1}$**。
:::info
**注意事項**：證明概念
在 $1$ 到 $p^e$ 中，與 $p^e$ **不互質**的數必為 $p$ 的倍數（即 $1p, 2p, \dots, p^{e-1}p$），共有 $p^{e-1}$ 個。全部扣除即得 $\phi(p^e)$。
:::
:::success
重點筆記：計算 $\phi(49)$。
- 不能用規則 3（因為 7 與 7 不互質），需用規則 4。
- $\phi(49) = \phi(7^2) = 7^2 - 7^1 = 49 - 7 = 42$。
:::
:::success
重點筆記：計算 $\phi(12)$
- $12 = 2^2 \times 3^1$。
- 方法一（列舉）：小於 12 且互質的數有 {1, 5, 7, 11}，共 4 個。
- 方法二（公式）：$\phi(12) = \phi(4) \times \phi(3) = (2^2 - 2^1) \times (3^1 - 3^0) = 2 \times 2 = 4$。
:::
**尤拉 phi 函數**：我們可以合併以上四個規則計算出 $\phi(n)$ 的值。舉例來說，如果 $n$ 可以分解成
$n = p_{1}^{e^1} \times p_{2}^{e^2} \times ... \times p_{k}^{e^k}$
### 01-03. 費馬小定理 (Fermat's Little Theorem)
若 $p$ 是質數，且 $a$ 與 $p$ 互質（$gcd(a, p)=1$）：
* **版本一**：$a^{p-1} \equiv 1 \pmod p$
* **版本二**：$a^p \equiv a \pmod p$ （對所有整數 $a$ 成立）
:::info
**證明概念**：餘數的重新排列
1. **建立數列**：假設 $p$ 是質數，$a$ 與 $p$ 互質。考慮一個包含 $(p-1)$ 個數的數列：
$$S = \{1\cdot a, \quad 2\cdot a, \quad 3\cdot a, \quad \dots, \quad (p-1)\cdot a\}$$
2. **取模運算 (Mod $p$)**：將數列 $S$ 中的每一個數都對 $p$ 取餘數，得到一個新的餘數集合 $R$。
3. **關鍵發現**：這個餘數集合 $R$ 其實就是 $\{1, 2, 3, \dots, p-1\}$ 的**重新排列 (Permutation)**。
也就是說，數列 $S$ 的餘數包含了 $1$ 到 $p-1$ 的所有整數，且每個數恰好出現一次。
> **為什麼？ (Why)**
> * **不會有 0**：因為 $a$ 和係數 $k$ ($1$ 到 $p-1$) 都與 $p$ 互質，相乘後不可能被 $p$ 整除。
> * **不會重複**：假設有兩個不同的係數 $j, k$ 使得 $j\cdot a \equiv k\cdot a \pmod p$。移項得 $(j-k)a \equiv 0 \pmod p$。因為 $a$ 與 $p$ 互質，所以必須是 $(j-k)$ 能被 $p$ 整除。但 $j, k$ 都小於 $p$，其差值不可能被 $p$ 整除，故假設錯誤，證明餘數皆相異。
4. **推導結果**：既然兩個集合的元素模 $p$ 後相同，那麼把它們**全部乘起來**，結果也應該同餘：
$$1 \cdot 2 \cdots (p-1) \cdot a^{p-1} \equiv 1 \cdot 2 \cdots (p-1) \pmod p$$
$$(p-1)! \times a^{p-1} \equiv (p-1)! \pmod p$$
消去兩邊的 $(p-1)!$ (因為它與 $p$ 互質)，即得證：
$$a^{p-1} \equiv 1 \pmod p$$
:::
:::success
**重點筆記**：指數運算
- **計算 $6^{10} \pmod{11}$**：因為 11 是質數，根據定理，$6^{11-1} \equiv 1 \pmod{11}$。
- **計算 $3^{12} \pmod{11}$**：
1. $3^{12} = 3^{11} \times 3^1$。
2. 根據版本二 $3^{11} \equiv 3 \pmod{11}$，故原式 $\rightarrow (3^{11} \text{mod} 11)(3 \text{mod} 11)\equiv 3 \times 3 = 9 \pmod{11}$。
:::
### 01-04. 計算乘法反元素
**乘法反元素：為什麼是 $a^{p-2}$**？利用費馬小定理，我們可以快速找到一個數在模 $p$ 下的倒數（反元素）。
:::success
**重點筆記**：
1. **費馬小定理告訴我們**：若 $p$ 是質數，則 $a^{p-1} \equiv 1 \pmod p$。
2. **將指數拆解**：我們可以把 $a^{p-1}$ 拆成 $a$ 乘以剩下的部分
$$a \times a^{p-2} \equiv 1 \pmod p$$
3. **對照反元素的定義**：反元素 $a^{-1}$ 的定義是：$a \times a^{-1} \equiv 1 \pmod p$。
4. **結論**：比較上述兩式，顯然 $a^{p-2}$ 就扮演了反元素的角色。因此得證
$$a^{-1} \equiv a^{p-2} \pmod p$$
若 $p$ 為質數，則 $a^{-1} \equiv a^{p-2} \pmod p$。
:::
:::success
**重點筆記**：快速求反元素
- **$8^{-1} \pmod{17}$**：$8^{17-2} = 8^{15} \equiv 15 \pmod{17}$。
- **$5^{-1} \pmod{23}$**：$5^{23-2} = 5^{21} \equiv 14 \pmod{23}$。
- **$60^{-1} \pmod{101}$**：$60^{99} \equiv 32 \pmod{101}$。
- **$22^{-1} \pmod{211}$**：$22^{209} \equiv 48 \pmod{211}$。
:::
### 01-04. 尤拉定理 (Euler's Theorem)
這是費馬小定理的推廣。若正整數 $a, n$ 互質：
* **版本一**：$a^{\phi(n)} \equiv 1 \pmod n$
* **版本二**：$a^{k \times \phi(n) + 1} \equiv a \pmod n$
:::info
**重點筆記**：尤拉定理的證明概念 (Proof Concept)
1. **定義互質集合**：假設 $n$ 為正整數，且 $a$ 與 $n$ 互質（$gcd(a, n) = 1$）。令集合 $S$ 為所有小於 $n$ 且與 $n$ 互質的正整數：
$$S = \{x_1, x_2, \dots, x_{\phi(n)}\}$$
此集合共有 $\phi(n)$ 個元素。
2. **建立新數列**：將集合 $S$ 中的每一個元素都乘上 $a$
$$S' = \{x_1 \cdot a, \quad x_2 \cdot a, \quad \dots, \quad x_{\phi(n)} \cdot a\}$$
3. **取模運算 (Mod $n$)**：將 $S'$ 中的數分別除以 $n$ 取餘數，得到集合 $R = \{r_1, r_2, \dots, r_{\phi(n)}\}$。
4. **關鍵發現**：集合 $R$ 其實是集合 $S$ 的**重新排列 (Permutation)**。也就是說，$R$ 中的餘數恰好就是 $S$ 中的那些數（$x_1$ 到 $x_{\phi(n)}$），只是順序可能不同。
> **為什麼？ (Why)**
> * **餘數互異**：對於 $S$ 中任意兩個相異元素 $x_i, x_j$，其差 $(x_i - x_j)$ 不是 $n$ 的倍數。因為 $a$ 與 $n$ 互質，故 $(x_i a - x_j a) = a(x_i - x_j)$ 也不會是 $n$ 的倍數，因此餘數不會重複。
> * **餘數不為 0**：因為 $a$ 與 $n$ 互質，且 $x_i$ 與 $n$ 互質，兩者乘積 $x_i a$ 也不會含有 $n$ 的因數，故餘數不為 0。
5. **推導結果**：既然 $R$ 和 $S$ 的元素相同（僅順序不同），將兩邊集合的所有元素相乘，結果在模 $n$ 下應相等：
$$(x_1 \cdot a) \cdot (x_2 \cdot a) \cdots (x_{\phi(n)} \cdot a) \equiv x_1 \cdot x_2 \cdots x_{\phi(n)} \pmod n$$
$$(\prod_{i=1}^{\phi(n)} x_i) \times a^{\phi(n)} \equiv (\prod_{i=1}^{\phi(n)} x_i) \pmod n$$
消去兩邊的 $\prod x_i$ (因為它們都與 $n$ 互質，可消去)，即得證：
$$a^{\phi(n)} \equiv 1 \pmod n$$
:::
:::success
**重點筆記**：指數降冪
- **$6^{24} \pmod{35}$**：
1. $\phi(35) = \phi(5)\phi(7) = 4 \times 6 = 24$。
2. 故 $6^{24} = 6^{\phi(35)} \equiv 1 \pmod{35}$。
- **$20^{62} \pmod{77}$**：
1. $\phi(77) = \phi(7)\phi(11) = 6 \times 10 = 60$。
2. $20^{62} = 20^{60} \times 20^2 \equiv 1 \times 400 \pmod{77}$。
3. $400 \div 77 = 5 \dots 15$，故答案為 **15**。
:::
**應用**：計算乘法反元素 (模數為合成數時)當模數 $n$ 是合成數時，我們可以使用尤拉定理求出乘法反元素
$$a^{-1} \pmod n \equiv a^{\phi(n)-1} \pmod n$$
:::success
**重點筆記**：利用尤拉定理求反元素
假設 $n=15$ (合成數)，求 $2$ 的反元素。
1. $\phi(15) = \phi(3) \times \phi(5) = 2 \times 4 = 8$。
2. 代入公式：$2^{-1} \equiv 2^{8-1} = 2^7 \pmod{15}$。
3. $2^7 = 128$。
4. $128 \div 15 = 8 \dots 8$。
5. 故 $2^{-1} \equiv 8 \pmod{15}$。 (驗算：$2 \times 8 = 16 \equiv 1$)
:::
### 01-05. 特殊質數 (Special Primes)
**莫仙尼質數 (Mersenne Primes)**：一個可以表示成 $M_p = 2^p - 1$ 的數值被稱為莫仙尼數。其可能是質數，也可能不是。
* $M_2 = 2^2 - 1 = 3$ (質數)
* $M_3 = 2^3 - 1 = 7$ (質數)
* $M_5 = 2^5 - 1 = 31$ (質數)
* $M_7 = 2^7 - 1 = 127$ (質數)
* $M_{11} = 2^{11} - 1 = 2047$ (**非質數**，因為 $2047 = 23 \times 89$)
* $M_{13} = 2^{13} - 1 = 8191$ (質數)
* $M_{17} = 2^{17} - 1 = 131071$ (質數)
**費馬質數 (Fermat Primes)**：一個可以表示成 $F_n = 2^{2^n} + 1$ 的數值被稱為費馬數。其有可能是質數，也可能不是。
* $F_1 = 2^{2^1} + 1 = 5$ (質數)
* $F_2 = 2^{2^2} + 1 = 17$ (質數)
* $F_3 = 2^{2^3} + 1 = 257$ (質數)
* $F_4 = 2^{2^4} + 1 = 65537$ (質數)
* $F_5 = 2^{2^5} + 1 = 4294967297$ (**非質數**，因為 $4294967297 = 641 \times 6700417$)
<br>
## 02. 質數測試法 (Primality Testing)
數論與密碼學的一大挑戰是找出能正確且有效率地判定大整數是否為質數的演算法。目前分為「確定式」與「機率式」兩類。
### 02-01. 確定式演算法 (Deterministic Algorithms)
這類演算法能給出 100% 正確的答案，但計算成本通常較高。
**整除性測試法 (Divisibility Test)**
```python=
Divisibility_Test (n) #1/測試n是否為質數
{
r <- 2
while (r < sqrt(n))
{
if (r|n) return "a composite"
r <- r+1
}
return "a prime"
}
```
- **方法**：測試所有小於 $\sqrt{n}$ 的質數是否能整除 $n$ 。
- **複雜度**：位元運算複雜度為 $2^{(\log_2 n)/2}$，呈現指數成長，對大數不可行 。
:::success
**重點筆記**：若 $n$ 有 200 個位元，此法約需 $2^{100}$ 次運算。即使電腦每秒執行 $10$ 億 ($2^{30}$) 次運算，仍需 $2^{70}$ 秒，時間成本過高
:::
**AKS 測試法 (Agrawal-Kayal-Saxena)**
- **定理**：正整數 $n \ge 2$ 是質數，若且唯若 $(x+1)^n - (x^n+1) \equiv 0 \pmod n$ 。
- **複雜度**：這是多項式時間演算法，複雜度為 $O((\log_2 n)^{12})$ 。
:::info
**注意事項**：證明攻勢
- 正整數 $n \ge 2$ 是質數，若且唯若以下多項式同餘恆等式成立：
$$(x+1)^n - (x^n+1) \equiv 0 \pmod n$$
- **理論基礎**：
1. 這個定理可以視為**費馬小定理的一般化**推廣。
2. 其證明主要基於**二項式係數**的特徵：對於任何 $0 < k < n$，二項式係數 $\binom{n}{k}$ 滿足：
$$\binom{n}{k} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{(n-k)!} \equiv 0 \pmod n$$
此條件成立 **若且唯若** $n$ 是質數。
:::
:::success
**重點筆記**：同樣針對 200 位元的 $n$，AKS 演算法僅需約 $4 \times 10^{10}$ 次運算，上述電腦約 40 秒即可完成
:::
### 02-02. 機率式演算法 (Probabilistic Algorithms)
這類演算法效率極高，雖然有極小機率誤判合成數為質數，但可透過多次測試將誤差降至極低。
**費馬測試法 (Fermat Test)**
- **原理**：若 $n$ 為質數，則 $a^{n-1} \equiv 1 \pmod n$。
- **缺陷**：存在 Carmichael Numbers（偽質數），它們是合成數但能通過測試。
:::success
**重點筆記**：檢測 561 (合成數 $33 \times 17$)，底數 $a=2$。
- 計算 $2^{561-1} \equiv 1 \pmod{561}$。
- 它通過了測試，但實際上是合成數。
:::
**平方根測試法 (Square Root Test)**
- **原理**：若 $n$ 是質數，則 $1 \pmod n$ 的平方根只有 $\pm 1$。若發現其他解，則 $n$ 必為合成數。
:::success
**重點筆記**：合成數的狀況
當 $n=7$ (質數) 時，1 在模 7 下的平方根為何？**解法**：平方根只有 **1** 和 **-1**。
- $1^2 \equiv 1 \pmod 7$； $(-1)^2 \equiv 1 \pmod 7$
- $2^2 \equiv 4 \pmod 7$； $(-2)^2 \equiv 4 \pmod 7$
- $3^2 \equiv 2 \pmod 7$； $(-3)^2 \equiv 2 \pmod 7$
- 只有 $\pm 1$ 的平方是 1。
當 $n=17$ (質數) 時，1 在模 17 下的平方根為何？ **解法**：平方根只有 **1** 和 **-1**。
- $1^2 \equiv 1 \pmod{17}$
- $2^2 \equiv 4 \pmod{17}$
- $3^2 \equiv 9 \pmod{17}$
- $4^2 \equiv 16 \pmod{17}$
- $5^2 \equiv 8 \pmod{17}$
- $6^2 \equiv 2 \pmod{17}$
- $7^2 \equiv 15 \pmod{17}$
- $8^2 \equiv 13 \pmod{17}$
- 結果顯示只有 $\pm 1$ 符合條件。
**當 $n=8$ (合成數)**：1 在模 8 下的平方根為何？
- $1^2 \equiv 1 \pmod 8$； $(-1)^2 \equiv 1 \pmod 8$
- $3^2 \equiv 1 \pmod 8$； $(-3)^2 \equiv 1 \pmod 8$
- $5^2 \equiv 1 \pmod 8$； $(-5)^2 \equiv 1 \pmod 8$
- **觀察**：出現了 $\pm 1$ 以外的根（如 3, 5），故可判定為合成數。
**當 $n=22$ (合成數)**：1 在模 22 下的平方根為何？
- $1^2 \equiv 1 \pmod{22}$
- $(-1)^2 \equiv 1 \pmod{22}$
:::
**Miller-Rabin 測試法** (工業標準)：結合費馬測試與平方根測試。
```python=
Miller_Rabin_ Test (n, a) # n is the number; a is the base.
{
Find m and k such that n - 1 = m x 2^k
T <- a^m mod n
if (T = +- 1) return "a prime"
for (i < 1 to k - 1) # k - 1 is the maximum number of steps.
{
T <- T^2 mod n
if (T = +1) return "a composite"
if (T = -1) return "a prime"
}
return "a composite"
}
```
- 演算法流程
1. 將 $n-1$ 表示為 $m \times 2^k$ ($m$ 為奇數)。
2. 計算 $T = a^m \pmod n$。
3. 若 $T = \pm 1$，回傳 "可能是質數" (prime)。
4. 重複 $k-1$ 次迴圈 (將 $T$ 平方)：
* $T \leftarrow T^2 \pmod n$
* 若 $T = 1$，回傳 "合成數" (composite)。（因為這代表前一次的 $T$ 是 1 的非平凡平方根）。
* 若 $T = -1$，回傳 "可能是質數" (prime)。
5. 若迴圈結束仍未回傳，則為 "合成數"。
:::info
**重點筆記**：Miller-Rabin 測試法的證明 (Proof)
**命題**：令 $n$ 為奇數，$n-1 = m \times 2^k$。若對於底數 $a$ 滿足以下兩個條件（即通過 Miller-Rabin 的合成數判斷條件）：
1. $a^m \not\equiv 1 \pmod n$
2. 對所有 $0 \le i < k$，$a^{2^i m} \not\equiv -1 \pmod n$
則 $n$ 必為 **合成數**。
**證明邏輯 (反證法)**：
- **假設 $n$ 是質數 $p$**：
1. 根據費馬小定理，$a^{p-1} \equiv 1 \pmod p$。
2. 因為 $p-1 = m \times 2^k$，所以序列的最後一項 $a^{m \cdot 2^k} \equiv 1 \pmod p$。
3. 在模 $p$ (質數) 下，方程式 $x^2 \equiv 1 \pmod p$ 只有兩個解：$x \equiv 1$ 或 $x \equiv -1$。
- **逆向開根號分析**：我們將序列 $a^{m \cdot 2^k}$ 往前一直取平方根（$a^{m \cdot 2^{k-1}}, \dots, a^m$），必然會遇到 $1$ 或 $-1$。會有兩種情況：
1. **情況 A**：在過程中遇到了 $-1$。這意味著存在某個 $0 \le i < k$ 使得 $a^{m \cdot 2^i} \equiv -1 \pmod p$ $\implies$ 這違反了命題中的條件 2（該條件說永遠不會出現 $-1$）。
2. **情況 B**：從頭到尾都沒有遇到 $-1$。既然最後是 $1$，且開根號只有 $\pm 1$ 兩種可能，若不出 $-1$，代表每次開根號的結果都是 $1$。這會一直推導回第一項，得到 $a^m \equiv 1 \pmod p$ $\implies$ 這違反了命題中的條件 1（該條件說 $a^m \not\equiv 1$）。
3. **結論**：
若命題中的條件 1 和 2 同時成立，則 $n$ 不可能是質數（因為質數必然會違反其中一項）。故 $n$ 必為合成數。
:::
:::success
**重點筆記**：測試 561 (底數 a=2)
1. $561-1 = 560 = 35 \times 2^4$。 ($m=35, k=4$)
2. **Init**: $T = 2^{35} \pmod{561} = 263$。
3. **k=1**: $T = 263^2 \pmod{561} = 166$。
4. **k=2**: $T = 166^2 \pmod{561} = 67$。
5. **k=3**: $T = 67^2 \pmod{561} = 1$。
6. **判定**：出現 1，但前一個數 (67) 不是 -1 (560)。判定為 **合成數**。
:::
:::success
**重點筆記**：測試 4033
- **底數 a=2 時**：
1. $4033-1 = 63 \times 2^6$。
2. $T = 2^{63} \equiv 3521$。平方後 $T^2 \equiv -1$。**通過測試 (Passes)**。
- **底數 a=3 時**：
1. $T = 3^{63} \equiv 3551$。
2. 隨後的平方序列為 $2443 \to 3442 \to 2443 \to 3442 \dots$
3. 從未出現 -1。判定為 **合成數 (Composite)**。
- **結論**：需多測幾個底數才能確信。
:::
<br>
## 03. 因數分解 (Factorization)
因數分解是許多公開金鑰密碼系統（如 RSA）安全性的基石。雖然算術基本定理保證了解的存在性，但對於極大的整數，尋找其質因數在計算上極為困難。
### 03-01. 算術基本定理 (Fundamental Theorem of Arithmetic)
- 任何大於 1 的正整數都可以唯一地分解為質數的乘積。
- 若整數 $a$ 和 $b$ 的質因數分解如下：
$$a = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$$
$$b = p_1^{b_1} \times p_2^{b_2} \times \cdots \times p_k^{b_k}$$
- 則我們可以利用指數來定義最大公因數與最小公倍數：
1. **最大公因數 (GCD)**：取指數的**最小值**。
$$gcd(a, b) = p_1^{\min(a_1, b_1)} \times p_2^{\min(a_2, b_2)} \times \cdots \times p_k^{\min(a_k, b_k)}$$
2. **最小公倍數 (LCM)**：取指數的**最大值**。
$$lcm(a, b) = p_1^{\max(a_1, b_1)} \times p_2^{\max(a_2, b_2)} \times \cdots \times p_k^{\max(a_k, b_k)}$$
**重要關係式**：
$$lcm(a, b) \times gcd(a, b) = a \times b$$
### 03-02. 試除法 (Trial Division)
這是最直觀的分解方法，適合處理較小的數字。
```python=
Trial_Division_Factorization (n) # n is the number to be factored
{
a <- 2
while (a ≤ sqrt(n))
{
while (n mod a = 0)
{
output a # Factors are output one by one
n = n / a
}
a <- a + 1
}
if (n > 1) output n # n has no more factors
}
```
* **演算法邏輯**：從整數 $a = 2$ 開始，測試是否能整除 $n$。
1. 若 $n \pmod a == 0$，則輸出 $a$ 為因數，並更新 $n \leftarrow n/a$（持續除到不能整除為止）。
2. 若 $a > \sqrt{n}$，則剩下的 $n$ 若大於 1，必為質數，直接輸出 $n$。
3. 否則 $a \leftarrow a + 1$，繼續測試。
:::success
**重點筆記**：分解大數
- 使用試除法找出 **1,523,357,784** 的所有因數。
- 執行程式後得到的結果為：
$$1523357784 = 2^3 \times 3^2 \times 13 \times 37 \times 43987$$
:::
### 03-03. 費馬分解法 (Fermat Factorization)
當一個奇數 $n$ 的兩個因數很接近時，此方法非常有效率。
**核心概念**：試圖將 $n$ 表示為兩個平方數的差：
- 其中 $a = (x+y)$ 與 $b = (x-y)$ 即為 $n$ 的因數。
$$n = x^2 - y^2 = (x + y)(x - y)$$
```python=
Feramat_Factorization (n) # n is the number to be factored
{
x <- sqrt(n) // smallest integer greater than In
while (x < n)
{
if(w is perfect square)
{
y <- sqrt(w);
a <- x + y;
b <- x - y;
return a and b
}
x <- x + 1
}
}
```
**演算法邏輯**：
- 設定 $x$ 的初始值為 $\lceil\sqrt{n}\rceil$（大於等於 $\sqrt{n}$ 的最小整數）。
- 進入迴圈（當 $x < n$）：
1. 計算 $w = x^2 - n$。
2. 檢查 $w$ 是否為完全平方數（即是否存在整數 $y$ 使得 $y^2 = w$）。
3. **若 $w$ 是完全平方數**：
* 計算 $y = \sqrt{w}$。
* 得到因數 $a \leftarrow x + y$，$b \leftarrow x - y$。
* 回傳 $a$ 和 $b$，結束。
4. **若不是**：
* $x \leftarrow x + 1$，繼續嘗試。
:::success
**重點筆記**：使用費馬分解法分解 $n = 5959$
- 計算 $\sqrt{5959} \approx 77.19$。初始 $x = 78$。
- **第一次測試 ($x=78$)**：
1. $w = 78^2 - 5959 = 6084 - 5959 = 125$。
2. $\sqrt{125}$ 不是整數，失敗。
- **第二次測試 ($x=79$)**：
1. $x \leftarrow 79$。
2. $w = 79^2 - 5959 = 6241 - 5959 = 282$。
3. 不是完全平方數，失敗。
- **第三次測試 ($x=80$)**：
1. $x \leftarrow 80$。
2. $w = 80^2 - 5959 = 6400 - 5959 = 441$。
3. $\sqrt{441} = 21$ (是完全平方數！)，故 $y=21$。
- **得出結果**：
1. $a = 80 + 21 = 101$
2. $b = 80 - 21 = 59$
3. 故 $5959 = 101 \times 59$。
:::
<br>
## 04. 中國餘數定理 (Chinese Remainder Theorem, CRT)
### 04-01. 概念 (Concept)
中國餘數定理是用來求解模數兩兩相異且互質（pairwise coprime）之單變數同餘方程組的方法。
**方程組形式**：其中 $m_1, m_2, \dots, m_k$ 兩兩互質。
$$
\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\dots \\
x \equiv a_k \pmod{m_k}
\end{cases}
$$
### 04-02. 求解演算法 (Algorithm)
根據範例 9.35 的解法，我們可以歸納出標準的求解步驟：
- **計算總模數**：求出所有模數的乘積 $M = m_1 \times m_2 \times \cdots \times m_k$。
- **計算部分模數**：對於每個 $i$，計算 $M_i = M / m_i$。
- **尋找乘法反元素**：在模 $m_i$ 下，找出 $M_i$ 的乘法反元素 $M_i^{-1}$，使得 $M_i \times M_i^{-1} \equiv 1 \pmod{m_i}$。
- **組合通解**：$$x = (a_1 \times M_1 \times M_1^{-1} + a_2 \times M_2 \times M_2^{-1} + \cdots + a_k \times M_k \times M_k^{-1}) \pmod M$$
### 04-03. 應用實例 (Examples)
**基礎求解：解方程組**
$$
\begin{cases}
x \equiv 2 \pmod 3 \\
x \equiv 3 \pmod 5 \\
x \equiv 2 \pmod 7
\end{cases}
$$
- 計算總模數 $M$：$$M = 3 \times 5 \times 7 = 105$$
- 計算部分模數 $M_i$ 與其反元素 $M_i^{-1}$：
1. 針對 $m_1 = 3$：
- $M_1 = M / m_1 = 105 / 3 = 35$
- 解 $35 \times y_1 \equiv 1 \pmod 3 \Rightarrow 2 \times y_1 \equiv 1 \pmod 3$
- 可得 $y_1 = 2$ (因為 $2 \times 2 = 4 \equiv 1$)，故 $M_1^{-1} = 2$。
2. 針對 $m_2 = 5$：
- $M_2 = M / m_2 = 105 / 5 = 21$
- 解 $21 \times y_2 \equiv 1 \pmod 5 \Rightarrow 1 \times y_2 \equiv 1 \pmod 5$
- 可得 $y_2 = 1$，故 $M_2^{-1} = 1$。
3. 針對 $m_3 = 7$：
- $M_3 = M / m_3 = 105 / 7 = 15$
- 解 $15 \times y_3 \equiv 1 \pmod 7 \Rightarrow 1 \times y_3 \equiv 1 \pmod 7$
- 可得 $y_3 = 1$，故 $M_3^{-1} = 1$。
4. 組合通解 $x$：$$\begin{aligned}
x &= (a_1 M_1 M_1^{-1} + a_2 M_2 M_2^{-1} + a_3 M_3 M_3^{-1}) \pmod M \\
&= (2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1) \pmod{105} \\
&= (140 + 63 + 30) \pmod{105} \\
&= 233 \pmod{105} \\
&= \mathbf{23}
\end{aligned}$$
- 驗算：$23 \div 3 = 7 \dots 2$， $23 \div 5 = 4 \dots 3$， $23 \div 7 = 3 \dots 2$。
- 其它例子
1. $x \equiv 2 \pmod 7$ 且 $x \equiv 3 \pmod 9 \implies \mathbf{x = 30}$。
2. $x \equiv 4 \pmod 5$ 且 $x \equiv 10 \pmod{11} \implies \mathbf{x = 54}$。
3. $x \equiv 7 \pmod{13}$ 且 $x \equiv 11 \pmod{12} \implies \mathbf{x = 59}$。
**大數運算應用**
- 假設系統限制運算數值需小於 100，我們可以使用 CRT 來計算大數加法 $z = x + y$，其中 $x=123, y=334$。
- **轉換為餘數系統 (Mod 99, 98, 97)**：
1. $x$ 的餘數：$24, 25, 26$。
2. $y$ 的餘數：$37, 40, 43$。
- **在餘數系統中相加**：
1. $z \equiv 24+37 = 61 \pmod{99}$。
2. $z \equiv 25+40 = 65 \pmod{98}$。
3. $z \equiv 26+43 = 69 \pmod{97}$。
- **還原解答**：利用 CRT 解出滿足上述三個餘數條件的 $z$，可得 **$z = 457$**。
<br>
## 05. 二次同餘 (Quadratic Congruence)
在密碼學中，我們經常討論形式為 $x^2 \equiv a \pmod n$ 的二次同餘方程式（其中 $a$ 為常數，$n$ 為模數）。
### 05-01. 二次剩餘 (Quadratic Residue, QR)
**核心概念**：什麼是 QR？在模數 $p$ 的世界裡，我們想知道整數 $a$ 是不是某個數的平方？也就是求解方程式：
$$x^2 \equiv a \pmod p$$
- **二次剩餘 (QR)**：$a$ 是「有解」的。也就是說，$a$ 是一個「完全平方數」。
- **非二次剩餘 (NQR)**：$a$ 是「無解」的。也就是說，找不到任何數平方後會等於 $a$。
:::success
**重點筆記**：解與同餘
- 解 $x^2 \equiv 3 \pmod{11}$：
- 兩個解為 $x \equiv 5 \pmod{11}$ 和 $x \equiv -5 \equiv 6 \pmod{11}$。
- 注意 $5$ 和 $6$ 是不同的解（非同餘）。
:::
:::success
**重點筆記**：$Z_{11}^*$ 的分佈
- 我們直接把 $Z_{11}^* = \{1, 2, \dots, 10\}$ 裡的所有數字拿來平方，看看結果會落在哪些數字上。
<center>
| $x$ | (原始數)$x^2$ | (平方運算)$\pmod{11}$ | (取模結果 $a$)結論 |
| :--: | :--: | :--: | :--: |
| 1 | 1 | 1 | 1 是 QR |
| 2 | 4 | 4 | 4 是 QR |
| 3 | 9 | 9 | 9 是 QR |
| 4 | 16 | 5 | 5 是 QR |
| 5 | 25 | 3 | 3 是 QR |
| 6 ($\equiv -5$) | 36 | 3 | (重複) |
| 7 ($\equiv -4$) | 49 | 5 | (重複) |
| 8 ($\equiv -3$) | 64 | 9 | (重複) |
| 9 ($\equiv -2$) | 81 | 4 | (重複) |
| 10 ($\equiv -1$) | 100 | 1 | (重複) |
</center>
- 在 $Z_{11}^* = \{1, 2, \dots, 10\}$ 中，元素剛好分為兩半：
- **QR set** (有平方根): $\{1, 3, 4, 5, 9\}$
- **NQR set** (無平方根): $\{2, 6, 7, 8, 10\}$
:::
### 05-02. 尤拉準則 (Euler's Criterion)
如何快速判斷 $a$ 是否為質數 $p$ 的 QR？
* 若 $a^{(p-1)/2} \equiv 1 \pmod p \implies$ $a$ 是 **QR** (有解)。
1. 若 $a$ 是二次剩餘，則存在 $x$ 使得 $x^2 \equiv a \pmod p$
2. 因此 $a^{(p-1)/2} = (x^2)^{(p-1)/2} = x^{p-1} \equiv 1 \pmod p$(費馬小定理)
* 若 $a^{(p-1)/2} \equiv -1 \pmod p \implies$ $a$ 是 **NQR** (無解)。
:::success
**重點筆記**：在 $Z_{23}^*$ 中檢查 14 和 16
- **檢查 14**：
1. 計算 $14^{(23-1)/2} = 14^{11} \pmod{23}$。
2. 結果為 $22 \equiv -1 \pmod{23}$ $\implies$ **14 是 NQR (無解)**。
- **檢查 16**：
1. 計算 $16^{(23-1)/2} = 16^{11} \pmod{23}$。
2. 結果為 $1 \pmod{23}$ $\implies$ **16 是 QR (有解)**。
:::
### 05-03. 求解二次方程式
**情況 A：模數 $p$ 是質數**
當模數 $p$ 是一個質數，且滿足 $p \equiv 3 \pmod 4$ (即 $p = 4k+3$) 時，求解 $x^2 \equiv a \pmod p$ 有一個非常簡單且高效的通解公式：
$$x \equiv \pm a^{(p+1)/4} \pmod p$$
- **數學證明 (Proof)**：我們需要證明 $x = a^{(p+1)/4}$ 確實是 $x^2 \equiv a \pmod p$
1. **代入驗證**： 將 $x$ 代入方程左邊進行平方：
$$x^2 \equiv (a^{(p+1)/4})^2 \equiv a^{(p+1)/2} \pmod p$$
2. **指數拆解**： 將指數 $(p+1)/2$ 拆解為 $(p−1)/2+1$：
$$a^{(p+1)/2} = a^{(p-1)/2} \cdot a^1$$
3. **應用尤拉準則 (Euler's Criterion)**： 前提是 $a$ 必須是二次剩餘 (QR)，否則方程本來就無解。 既然 $a \in QR$，根據尤拉準則：
$$a^{(p-1)/2} \equiv 1 \pmod p$$
4. **推導結果**：得證
$$x^2 \equiv 1 \cdot a \equiv a \pmod p$$
- **Blum Blum Shub 應用**：此性質在密碼學中有重要應用。當 $p \equiv 3 \pmod 4$ 時，二次剩餘的運算具有封閉性或特定的排列特性，這對於設計如 Blum Blum Shub 這類基於數論困難問題的偽隨機數生成器（PRNG）至關重要，能增加亂數週期的複雜度與安全性。
:::success
**重點筆記**：求解練習
- **$x^2 \equiv 3 \pmod{23}$**：
1. $p=23$ 是 $4k+3$ 型。3 是 QR。
2. 解 $x \equiv \pm 3^{(23+1)/4} = \pm 3^6 = \pm 16 \pmod{23}$。
3. **代公式**：指數為 $(23+1)/4 = 6$。
4. **計算**：$x \equiv \pm 3^6 \equiv \pm 729 \pmod{23}$。
5. **化簡**：$729 \div 23 = 31 \dots 16$。
6. **答案**：$x \equiv \pm 16 \pmod{23}$。
- **$x^2 \equiv 2 \pmod{11}$**：
1. $2^{(11-1)/2} = 2^5 = 32 \equiv 10 \equiv -1$。
2. **無解 (NQR)**。
- **$x^2 \equiv 7 \pmod{19}$**：
1. $p=19$ 是 $4k+3$ 型。7 是 QR。
2. 解 $x \equiv \pm 7^{(19+1)/4} = \pm 7^5 \equiv \pm 11 \pmod{19}$。
3. 代公式：指數為 $(19+1)/4 = 5$。
4. 計算：$x \equiv \pm 7^5 \pmod{19}$。
5. 化簡：$7^5 = 16807$，除以 19 餘 11。
6. 答案：$x \equiv \pm 11 \pmod{19}$。
- $x^2 \equiv 4 \pmod 7$
1. 觀察：$4$ 本身就是 $2^2$，這題可以直觀求解。
2. 或代公式 ($p=7$ 為 $4k+3$ 型)：$x \equiv \pm 4^{(7+1)/4} \equiv \pm 4^2 \equiv \pm 16 \pmod 7$。
3. $16 \div 7 = 2 \dots 2$。
4. 解答：$x \equiv \pm 2 \pmod 7$ (即 $2$ 和 $5$)。
- $x^2 \equiv 5 \pmod{11}$ ($p=11$ 為 $4k+3$ 型)
1. $x \equiv \pm 5^{(11+1)/4} \equiv \pm 5^3 \pmod{11}$。$5^3 = 125$。
2. $125 = 11 \times 11 + 4 \implies 125 \equiv 4$。
3. 解答：$x \equiv \pm 4 \pmod{11}$ (即 $4$ 和 $7$)。
- $x^2 \equiv 7 \pmod{13}$
1. 判斷 QR計算 $7^{(13-1)/2} = 7^6 \pmod{13}$。
2. $7^2 = 49 = 3 \times 13 + 10 \equiv -3$。
3. $7^6 = (7^2)^3 \equiv (-3)^3 = -27$。
4. $-27 \equiv \mathbf{-1} \pmod{13}$。
5. 解答：結果為 $-1$，代表 $7$ 是 NQR，故無解 (No Solution)。
- 求解 $x^2 \equiv 12 \pmod{17}$
1. 判斷 QR計算 $12^{(17-1)/2} = 12^8 \pmod{17}$。
2. 技巧：$12 \equiv -5 \pmod{17}$，計算 $(-5)^8 = 5^8$ 比較快。
3. $5^2 = 25 \equiv 8$。
4. $5^4 \equiv 8^2 = 64 = 3 \times 17 + 13 \equiv -4$。
5. $5^8 \equiv (-4)^2 = 16 \equiv \mathbf{-1}$。
6. 解答：結果為 $-1$，代表 $12$ 是 NQR，故無解 (No Solution)。
:::
**情況 B：模數 $n$ 是合成數**
這也是 Rabin 密碼系統 解密時的核心步驟。當 $n = p \times q$ 時，求解 $x^2 \equiv a \pmod n$ 無法直接運算，必須採用「分治法 (Divide and Conquer)」。求解三步驟：
1. **分解 (Decompose)**：將問題拆解為兩個模質數的子問題。$x^2 \equiv a \pmod p$$x^2 \equiv a \pmod q$
2. **求解 (Solve)**：利用前一節（情況 A）的方法，分別解出 $x_p$ 和 $x_q$。
3. **組合 (Combine)**：利用 中國餘數定理 (CRT) 將 $(x_p, x_q)$ 的組合還原為模 $n$ 下的解。
:::success
**合成數求解**：解 $x^2 \equiv 36 \pmod{77}$ (其中 $77 = 7 \times 11$)。
Step 1 & 2: 分解並求解子問題
- 模 7 部分：$x^2 \equiv 36 \pmod 7 \implies x^2 \equiv 1 \pmod 7$。解為 $x \equiv \pm 1$ (即 $1$ 和 $6$)。
- 模 11 部分：$x^2 \equiv 36 \pmod{11} \implies x^2 \equiv 3 \pmod{11}$。觀察 $5^2 = 25 = 2 \times 11 + 3$，故 $x^2 \equiv 3$ 的解為 $\pm 5$。解為 $x \equiv \pm 5$ (即 $5$ 和 $6$)。
Step 3: CRT 組合求解我們有四組解 $(a_1, a_2)$ ：$(1, 5), (1, -5), (-1, 5), (-1, -5)$。
- CRT 參數準備：
1. $M = 77$
2. $M_1 = 77/7 = 11$。求 $11^{-1} \pmod 7 \implies 4^{-1} \equiv 2$ (因 $4 \times 2 = 8 \equiv 1$)。
3. $M_2 = 77/11 = 7$。求 $7^{-1} \pmod{11} \implies 7^{-1} \equiv 8$ (因 $7 \times 8 = 56 \equiv 1$)。
4. 通解公式：$$x = (a_1 \cdot 11 \cdot 2 + a_2 \cdot 7 \cdot 8) \pmod{77}$$$$x = (22 a_1 + 56 a_2) \pmod{77}$$
代入四種組合：
- $(1, 5)$: $22(1) + 56(5) = 22 + 280 = 302 \equiv \mathbf{71} \pmod{77}$
- $(1, -5)$: $22(1) + 56(-5) = 22 - 280 = -258 \equiv \mathbf{50} \pmod{77}$
- $(-1, 5)$: $22(-1) + 56(5) = -22 + 280 = 258 \equiv \mathbf{27} \pmod{77}$
- $(-1, -5)$: $22(-1) + 56(-5) = -22 - 280 = -302 \equiv \mathbf{6} \pmod{77}$
最終答案：$x$ 的四個解為 6, 27, 50, 71。(驗算：$6^2 = 36$，正確！)
:::
**安全性結論**：求解合成數模數的二次同餘式之難度，等同於對該模數進行因數分解。若 $n$ 很大且難以分解，則此問題在計算上是不可行的。
<br>
## 06. 指數運算與對數運算 (Exponentiation & Logarithm)
本節探討兩個互為反向的運算：
1. **指數運算**：$y = a^x \pmod n$。這在計算上是**容易**的（即使數字很大）。
2. **離散對數運算**：已知 $y, a, n$，求 $x$ 使得 $y \equiv a^x \pmod n$。這在計算上是**困難**的（對於大質數 $n$，目前沒有多項式時間的解法）。
### 06-01. 快速指數運算 (Square-and-Multiply)
直接計算 $a^x$ 會導致數值過大溢出，且運算次數隨指數線性成長。使用「平方暨乘法」可將複雜度降至多項式時間（與指數的位元數成正比）。
**演算法邏輯 (Algorithm)**：
```python=
Square _and_Multiply (a, x, n)
{
y <- 1
for (i <- 0 to nb - 1) # nb is the number of bits in x
{
if (xi = 1) y <- a x y mod n # multiply only if the bit is 1
a <- a^2 mod n # squaring is not needed in the last iteration
}
return y
```
- 將指數 $x$ 表示為二進位形式 $x = (x_{n_b-1} \dots x_1 x_0)_2$。
1. 初始化結果 $y \leftarrow 1$。
2. 從最高位 (MSB) 往最低位 (LSB) 掃描，或反之（視實作而定，通常從 LSB 到 MSB 為 $a \leftarrow a^2$ 的迭代）。
- **平方 (Square)**：每一輪都將底數平方 $a \leftarrow a^2 \pmod n$。
- **乘法 (Multiply)**：如果當前位元 $x_i = 1$，則累乘結果 $y \leftarrow y \times a \pmod n$。
:::info
**注意事項**
圖示流程 9.6 與 9.7 展現的是「從 MSB 往 LSB」的邏輯：遇到位元先 Square $y \leftarrow y^2$，若位元為 1 再 Multiply $y \leftarrow y \times a$。但表 9.3 使用的是「從 LSB 往 MSB」的邏輯。兩種皆可，結果相同。
:::
:::success
**重點筆記**：計算 $y = a^{22}$。
- 指數 $x = 22 = (10110)_2$，共 5 個位元。
- 流程圖路徑：Init $\to$ Square ($a^1$) $\to$ Multiply ($x_4=1$) $\to$ Square ($a^2$) $\to$ Square ($a^4$) $\to$ Multiply ($x_2=1$) $\to$ Square ($a^8$) $\to$ Multiply ($x_1=1$) $\to$ Square ($a^{16}$).
:::
:::success
**重點筆記**：計算 $17^{22} \pmod{21}$
- 採用 **LSB 到 MSB** 的方法 ($x=10110_2$, $x_0 \to x_4$):
| $i$ | 位元 $x_i$ | 乘法 (若 $x_i=1$, $y \leftarrow y \times a$) | 平方 (每輪 $a \leftarrow a^2$) |
| :--- | :---: | :--- | :--- |
| 0 | 0 | 不變 ($y=1$) | $17^2 \equiv 16 \pmod{21}$ |
| 1 | 1 | $y = 1 \times 16 = 16$ | $16^2 = 256 \equiv 4 \pmod{21}$ |
| 2 | 1 | $y = 16 \times 4 = 64 \equiv 1$ | $4^2 = 16 \pmod{21}$ |
| 3 | 0 | 不變 ($y=1$) | $16^2 \equiv 4 \pmod{21}$ |
| 4 | 1 | $y = 1 \times 4 = 4$ | (最後一輪不需平方) |
- **結果**：$17^{22} \equiv 4 \pmod{21}$。
:::
:::success
**重點筆記**：計算 $21^{24} \pmod 8$
- $21 \equiv 5 \pmod 8$。
- 觀察特徵：$5^2 = 25 \equiv 1 \pmod 8$。
- 故 $21^{24} \equiv 5^{24} = (5^2)^{12} \equiv 1^{12} = 1$。
- **Answer = 1**。
:::
### 06-02. 離散對數 (Discrete Logarithm)
**問題定義**：給定質數 $n$，底數 $a$，以及數值 $y$，求 $x$ 滿足 $y \equiv a^x \pmod n$。
**暴力搜尋法 (Brute Force)**：
```python=
Modular_Logarithm (a, y, n)
{
for (x = 1 to n-1)
{
if (y = a^x mod n) return x
}
return failure
}
```
1. 從 $x=1$ 試到 $n-1$。
2. 檢查 $y \equiv a^x \pmod n$ 是否成立。
3. **複雜度**：$O(n)$。當 $n$ 為 200 位元的大數時，此方法不可行。
4. 這種計算上的不對稱性（指數易、對數難）是 Diffie-Hellman 與 ElGamal 等密碼系統的安全基礎。
Sign in with Wallet
Connect another wallet