# Chapter4 - 數論與密碼學 Number Theory and Cryptography

## 整除性與模算術 Divisibility and Modular Arithmetic

* 整除性
* 令 $a, b \in \mathbb{Z}$ 且 $a \neq 0$
$a|b \equiv a \text{ divides } b \equiv \exists c \in \mathbb{Z} : b=ac$
* 例 : $3|-12 \Longleftrightarrow \text{True}$，但 $3|7 \Longleftrightarrow \text{False}$
* 定理 : $\forall a, b, c \in \mathbb{Z}$
* $a|0$
* $(a|b \wedge a|c) \rightarrow a|(b+c)$
* $a|b \rightarrow a|bc$
* $(a|b \wedge b|c) \rightarrow a|c$

* 除法定理 the division algorithm
* 對於被除數 $a$ 和除數 $d \neq 0$ ，有一組唯一的商 $q$ 和餘數 $r$
* $a = dq + r$ 且 $0 ≦ r < |d|$
* $a$ **div** $d$ = $q$ ； $a$ **mod** $d$ = $r$
* 餘數 $r$ **不能**為負數，例 : $-11=3 \times (-4) + 1$，因此 $-11$ **mod** $3 = 1$

* 模算術
* 定理 : $a \equiv b \text{ (mod m) if and only if } a \text{ mod } m = b \text{ mod } m$
* 螺旋可視化
> 可利用兩數相減判斷兩數取模後的值是否一樣 (兩數相減 = 模的倍數)
> 例題 : 判斷模6時，17是否同餘5
>
> $Ans:$ 是，因為17-5=12為6的倍數

* 公式
* 同餘定理 congruence theorems
> 若 $a \equiv b \text{ (mod m)}$ ，且 $c \equiv d \text{ (mod m)}$
> (以 $a$ = 7；$b$ = 2；$c$ = 11；$d$ = 1；$m$ = 5 為例)
* $a+c \equiv b+d \text{ (mod m)}$，例 : $7+11 \equiv 2 + 1 \text{ (mod 5)}$
* $ac \equiv bd \text{ (mod m)}$，例 : $7 \cdot 11 \equiv 2 \cdot 1 \text{ (mod 5)}$
* $a+b \equiv (a \text{ mod } m) + (b \text{ mod } m)$
* $ab \equiv (a \text{ mod } m)(b \text{ mod } m)$
* 算術模數*m* arithmetic modulo *m*
* $a+_mb = (a+b) \text{ mod } m$，例 : $7+_{11}9 = (7+9) \text { mod } 11 = 16 \text { mod } 11 = 5$
* $a \cdot _mb = (a \cdot b) \text{ mod } m$，例 : $7 \cdot _{11}9 = (7 \cdot 9) \text { mod } 11 = 63 \text { mod } 11 = 8$

## 質數與最大公因數 Prime & GCD
* 試除法 trial division
* 給定一個待分解的正整數n，試除法是用小於等於 $\sqrt n$ 的每個質數去試除。如果找到一個數能夠整除除盡，這個數就是可分解整數的因數，反之這個數為質數

* 梅遜質數 Mersenne primes
* 在過去300年來，最大的質數可被表示為 $2^p - 1$ ($p$亦是質數)，這些質數被稱為梅遜質數
* 例 : $2^2-1 = 3$、$2^5-1 = 31$ 這些可被稱為梅遜質數，但 $2^{11} - 1 = 2047$ 不是，因為 $2047 = 23 \times 89$
* 目前已知最大的梅遜質數為 $2^{136\ 279\ 841}-1$，共有41,024,320位數(2024年10月21日)

* 質數定理 the prime number theorem
* 質數在正整數中的出現沒有什麼規律。可是總體地看，質數的個數竟然有規可循
* **小於或等於 $x$ 的質數個數**與 **$\frac{x}{ln(x)}$** 的比值會趨近於1

* 哥德巴赫猜想 Goldbach's conjecture
* 任一大於2的偶數，都可表示成兩個質數之和
* 截至2014年，數學家已經驗證了 $4 \times 10^{18}$ 以內的偶數

* 孿生質數猜想 the twin prime conjecture
* 孿生質數是指一對相差2的質數(如 : 3與5)，猜想聲稱這樣的孿生質數有無限多對
* 目前已知最大的孿生質數為 $2\ 996\ 863\ 034\ 895\times 2^{1\ 290\ 000}\pm 1$，共有388,342位數(2016年9月)

* 最大公因數與最小公倍數 GCD & LCM
* 公式 : $ab = gcd(a,b) \times lcm(a,b)$
* 歐基里德演算法 Euclidean algorithm :
* $gcd(a,b) = gcd((a \ mod \ b),b)$
* 令 $a=bq+r$ ，則 $gcd(a,b) = gcd(b,r)$

* 最大公因數的線性組合 gcd as linear combinations
* 貝祖定理 Bezout theorem
* $gcd(a,b) = sa+tb$ ($s$和$t$ 為貝祖係數)
* 例 : 12和42的最大公因數是6，因此 $12s+42t=6$ 有解
* 若兩數互質， $gcd(a,b) = 1$ ，則 $sa+tb=1$
* 若 $ac \equiv bc \text{ (mod m)}$ 且 $gcd(c,m)=1$ ，則 $a \equiv b \text{ (mod m)}$

## 線性同餘解 Solving Congruences
* 解 $ax \equiv b$ (mod m) 方程式時，需先找出 $a$ 的反元素 $\overline a$ ， $a \overline a \equiv 1$，接著在等號兩邊乘以 $\overline a$ 即可找出 $x$

* 如果 $a$ 和 $m$ 互質，且 $m>1$ ，就可以找出 $a$ 的唯一反元素 $\overline a$

* 例題 : 找出3 mod 7的反元素

$Ans :$
因為 $gcd(3,7) = 1$，所以我們可以找出3 mod 7的反元素
$7 = 2 \cdot 3 + 1 \Longrightarrow -2 \cdot 3 + 1 \cdot 7 = 1$
得知3和7的貝祖係數分別為-2和1，因此 **$-2$ 為3 mod 7的反元素**

* 例題 : 求 $3x \equiv 4 \text{ (mod 7)}$

$Ans :$
由上個例題我們可知 $-2 \cdot 3x \equiv -2 \cdot 4 \text{ (mod 7)}$
因為 $-6 \equiv 1 \text{ (mod 7)}$ 且 $-8 \equiv 6 \text{ (mod 7)}$
所以 $x \equiv -8 \equiv 6 \text{ (mod 7)}$
我們將 $x \equiv -8$ 和 $x \equiv 6$ 帶入原式
$$
\begin{cases}
3 \cdot -8 = -24 \not\equiv 4 \text{ (mod 7) [不合]} \\
3 \cdot 6 = 18 \equiv 4 \text{ (mod 7) [合]} \\
\end{cases}
$$
$\therefore x \equiv 6 \text{ (mod 7) or } x = 6+7t, t \in \mathbb Z$

* 例題 : 找出29 mod 73的反元素及求出 $29x \equiv 4 \text{ (mod 73)}$ 的線性同餘解

$Ans :$
$1 = 2 \times 73 - 5 \times 29 \Longrightarrow$ -5是29 mod 73的反元素
$\therefore 73t + 68, t \in \mathbb Z$ 是29 mod 73的反元素 $(73-(-5)=68)$

$$
\begin{align*}
& 29x \equiv 4 \text{ (mod 73)} \\
& \Rightarrow { } 68 \times 29x \equiv 68 \times 4 \text{ (mod 73)} \\
& \Rightarrow { } (1971+1)x \equiv 272 \text{ (mod 73)} \\
& \Rightarrow { } (27 \times 73 + 1)x \equiv 53 \text{ (mod 73)} \\
& \Rightarrow { } x \equiv 53 \text{ (mod 73) or } x = 73t + 53, t \in \mathbb Z
\end{align*}
$$

* 中國餘數定理 the Chinese remainder theorem
* 公式 :
* $M_k = m / m_k$
* $M_ky_k \equiv 1 \text{ (mod m_k)}$
* $x = a_1M_1y_1 + a_2M_2y_2 + \ldots + a_nM_ny_n$
* $x \equiv a_kM_ky_k \equiv a_k \text{ (mod m_k)}$

* 例題 : 求下列線性同餘解
> $$
\begin{align}
& x \equiv 7 \ \text{ (mod 9)} \\
& x \equiv 4 \ \text{ (mod 12)} \\
& x \equiv 16 \text{ (mod 21)} \\
\end{align}
$$

$Ans :$
$$
\begin{align}
& x \equiv 7 \ \text{ (mod 9)} \rightarrow x \equiv 1 \text{ (mod 3) and } x \equiv 1 \text{ (mod 3)} \\
& x \equiv 4 \ \text{ (mod 12)} \rightarrow x \equiv 1 \text{ (mod 3) and } x \equiv 0 \text{ (mod 4)} \\
& x \equiv 16 \text{ (mod 21)} \rightarrow x \equiv 1 \text{ (mod 3) and } x \equiv 2 \text{ (mod 7)}\\
\end{align}
$$

We see that our system is equivalent to $x \equiv 7 \ \text{ (mod 9), }x \equiv 0 \text{ (mod 4), }x \equiv 2 \text{ (mod 7)}$

$x = a_1M_1y_1 + a_2M_2y_2 + a_3M_3y_3$
$a_1 = 7, a_2 = 0, a_3 = 2$
$M_1 = \frac{9 \times 4 \times 7}{9} = 28, M_2 = \frac{9 \times 4 \times 7}{4} = 63, M_3=\frac{9 \times 4 \times 7}{7} = 36$

$$
\begin{align}
& M_1y_1 \equiv 1 \text{ (mod 9)} \Rightarrow 28y_1 \equiv 1 \text{ (mod 9)} \Rightarrow y_1 = 1 \\
& M_3y_3 \equiv 1 \text{ (mod 7)} \Rightarrow 36y_3 \equiv 1 \text{ (mod 9)} \Rightarrow y_3 = 1 \\
\end{align}
$$

$\therefore x = 7 \times 28 \times 1 + 0 \times M_2 \times y_2 + 2 \times 36 \times 1 = 268$
$268 \text{ mod } (9 \times 4 \times 7) = 16 \text{ mod } 252$
$\therefore x \equiv 16 \text{ (mod 252) or } x = 252t+16, t \in \mathbb Z$

* 費馬小定理 Fermat's little theorem
* 公式 : $a^p \equiv a(\text{mod } p)$ ( $p$ 為質數且 $a$ 為無法被 $p$ 整除之整數)
* 例題 : $7^{222} \text{ mod 11}$
$Ans : 7^{222} = 7^{22 \times 10 + 2} = (7^{10})^{22} \times 7^2 \equiv 1^{22} \times 49 \equiv 5 \text{ (mod 11)}$

* 擬質數 pseudoprimes
* 定義 : 令 $b$ 為整數。若 $n$ 為一合數，且 $b^{n-1} \equiv 1 \text{ (mod n)}$ ，則 $n$ 可被稱為以 $b$ 為底的擬質數
* 由來 : 古代中國數學家相信， $n$ 為基質數，若且唯若 $2^{n-1} \equiv 1 \text{ (mod }n \text)$ ，但中國數學家只有部分正確，上述方法有缺陷，有些合數可以經過檢驗，稱為擬質數。例 : 341為一擬質數，因為 $341 = 11 \times 31$ ，且 $2^{340} \equiv 1 \text{ (mod 341)}$

* 元根 primitive
* 定義 : 若 $r$ 為模 $p$ 的元根，則對於所有 $a \in \mathbb Z_p$ ，存在某個指數 $k$ ，使得 $a \equiv r^k \text{ (mod } p \text )$。簡單來說， **$r$ 是能生成所有非零餘數的數字**
* 例題 : 判斷2和3是否為模11的元根
$Ans :$
* 計算在 $\mathbb Z_{11}$ 中2的冪次 :
$2^1 = 2$ 、 $2^2 = 4$ 、 $2^3 = 8$ 、 $2^4 = 5$ 、 $2^5 = 10$ 、 $2^6 = 9$ 、 $2^7 = 7$ 、 $2^8 = 3$ 、 $2^9 = 6$ 、 $2^{10} = 1$
因為所有 $\mathbb Z_{11}$ 中的元素都能表示成2的冪次，**所以2為 $\mathbb Z_{11}$ 的元根**

* 計算在 $\mathbb Z_{11}$ 中3的冪次 :
$3^1 = 3$ 、 $3^2 = 9$ 、 $3^3 = 5$ 、 $3^4 = 4$ 、 $3^5 = 1$ 、 $3^6 = 3$ 、 $\ldots$
我們發現這樣的情況會在接下來求3的冪次中重複，便不再繼續
因為並非所有 $\mathbb Z_{11}$ 中的元素都能表示成3的冪次，**所以3不為 $\mathbb Z_{11}$ 的元根**

* 離散對數 discrete logarithms
* 若 $r^e \text{ mod } p = a$ 且 $1≦e≦-1$，則 $e$ 為 $a$ 以 $r$ 為底的模 $p$ 離散對數，記作 $log_r a = e$ ($p$ 為質數， $r$ 是模 $p$ 的元根， $a$ 是介於1到 $p-1$ 間的整數)
* 例題 : 求3和5以2為底的模11離散對數
$Ans :$ 在 $\mathbb Z_{11}$ 中， $2^8 = 3$ 及 $2^4 = 5$ ，所以答案分別是8和4，記作 $log_2 3 = 8$ 和 $log_2 5 = 4$

## 同餘應用 Application of Congruences
* 雜湊函數 hashing function
* 最常被使用的散置函數為 $h(k) = k \text{ mod } m$ ，其中 $m$ 為可使用之記憶體位置個數
* 雜湊函數應該要映成的，這樣所有記憶位置才可能使用到
* 例題 : 利用 $h(k) = k \text{ mod } 111$ 找出 $064\ 212\ 848$ 與 $037\ 149\ 212$ 的記憶位置分配
$Ans :$
* $h(064212848) = 064212848 \text{ mod } 111 = 14 \Longrightarrow$ 因此記憶位置在14
* $h(037149212) = 037149212 \text{ mod } 111 = 65 \Longrightarrow$ 因此記憶位置在65

* 擬隨機數 pseudorandom number
* 電腦模擬經常要隨機選數，因為系統方法產生之數字並非隨機，因此稱為擬隨機數
* 通常使用線性同餘， $x_{n+1} = (ax_n + c) \text{ mod } m$

* 檢查碼 check digits
* 有一些編碼會有檢查碼，如 : UPC、ISBN、信用卡號碼等，檢查碼通常使用同餘來驗證
* 以UPC為例，驗證方法為 $3x_1 + x_2 + 3x_3 + x_4 + 3x_5 + x_6 + 3x_7 + x_8 + 3x_9 + x_{10} + 3x_{11} + x_{12} \equiv 0 \text{ (mod 10)}$

## 密碼學 Cryptography

* 位移密碼 shift ciphers : 將字母位置移動 $k$ 個位置
* 加密函數 : $f(p) = (p + k) \text{ mod } 26$
* 解密函數 : $f^{-1}(p) = (p - k) \text{ mod } 26$
> 整數 $k$ 被稱為金鑰(key)

* 仿射密碼 affine ciphers : 位移密碼的一種特殊形式
* 加密函數 : $f(p) = (ap + b) \text{ mod } 26$
> $f$ 必須為雙射，因此 $gcd(a, 26) = 1$
* 解密同餘 : $p \equiv \overline a (c - b) \text{ (mod 26)}$

* 區塊密碼 block ciphers
* 單套字母密碼 : 將字母表中的每個字母替換成另一個字母的密碼
* 區塊密碼將字母區塊替換為其他字母區塊，以避免被使用常用字母分析破解

* 轉置密碼 transposition ciphers : 區塊密碼的一種
* 金鑰 : 集合 $\{1, 2, 3, \ldots , m \}$ 的置換 $\sigma$
* 加密 : $c_1, c_2, c_3, \ldots , c_m = p_{\sigma (1)}, p_{\sigma (2)}, p_{\sigma (3)}, \ldots , p_{\sigma (m)}$
* 解密 : 使用 $\sigma^{-1}$
* 例題 : $\sigma (1) = 3 \ , \ \sigma (2) = 1 \ , \ \sigma (3) = 4 \ , \ \sigma (4) = 2$
1. 加密 **PIRATE ATTACK**
2. 解密 **SWUE TRAEOEHS**

$Ans :$
1. 每四個字母分為一個區塊 **PIRA TEAT TACK**，再用 $\sigma$ 轉置成 **IPAR ETTA AKTC**
2. 找出 $\sigma ^{-1}$ 得到 $\sigma ^{-1}(1) = 2 \ , \ \sigma ^{-1}(2) = 4 \ , \ \sigma ^{-1}(3) = 1 \ , \ \sigma ^{-1}(4) = 3$ ，並應用到字串得到 **USEW ATER HOSE**，在分割文字後得到解答 **USE WATER HOSE**

* 密碼系統 cryptosystems
* 定義 : 一個密碼系統是一個五元組(five-tuple) $(P, C, K, E, D)$
* $P$ : 明文(plaintext)字串
* $C$ : 密文(ciphertext)字串
* $K$ : keyspace (所有可能金鑰集合)
* $E$ : 加密函數
* $D$ : 解密函數

* 加密函數 $E$ 對應的金鑰 $k$ 表示為 $E_k$，$E_k$ 的解密結果由 $D_k$ 表示，因此對所有明文字串 $p$ 來說， $D_k(E_k(p)) = p$

* RSA密碼系統 RSA cryptosystem
* RSA 加密
> 公鑰 : $(n,e)$
> * $n=pq$ : $p$ 、 $q$ 為兩個大質數
> * $e$ : 和 $(p-1)(q-1)$ 互質
---
1. 將明文訊息 $M$ 翻譯成由兩位整數組成的序列，分別代表字母。例如:用 $00$ 代表 $A$，$01$ 代表 $B$，依此類推
2. 將兩位整數連接成數字字串
3. 將此字串分割成大小相等的 $2N$ 位元數字區塊 其中 $2N$ 是 2525…25 中最大的偶數，且該偶數不超過 $n$ 位
4. 明文訊息 $M$ 現在是一個整數序列 $m1, m2, \ldots, mk$
5. 每個資料區塊（一個整數）都使用以下函數進行加密： $c = m^e \ mod \ n$

* RSA 解密
> 私鑰 : $(d,n)$
> * $d$ : 為 $e \ mod \ (p-1)(q-1)$ 的反元素
---
1. 我們可以使用以下公式解密每個資料塊： $m = c^d \ mod \ p \cdot q$

* RSA之所以能作為公鑰系統運行，是因為目前已知的唯一尋找 $d$ 的方法是基於將 $n$ 分解成質數。目前還沒有可行的將大數分解成質數的方法