---
tags : '資安'
---

# ch8 進階數論

數論的研究對公鑰的設計很重要，其中資安會著重在對於質數的研究

## 質數
任何大於1的整數都可以唯一被質因數分解為
其中$p_1<p_2<...<p_t$

### Fermat's Theorem(費馬小定理)

a^p-1^ ≡ 1 (mod p) → a和p互質時成立
a^p^ ≡ a (mod p)→ 不限制

### Euler's Totient Function(尤拉函數)

Φ(n) 定義: 比n小的正整數中，與n互質的整數個數
Ex: Φ(37)=36

* 給定兩個質數p、q，且 $p \neq q$ 令n = pq
則 $\varnothing(n) = \varnothing(pq) = \varnothing(p) * \varnothing(q) = (p-1) * (q-1)$

### Euler's Theorem(尤拉定理)

設兩正整數 a,n 且 gcd(a, n) = 1(互質)
則a^ø(n)^ ≡ 1(mod n) (a與n互質)
→a^ø(n)+1^ ≡ a(mod n) (a與n不須互質)

:::info
:bulb: 跟費馬定理很像，第一條需要兩整數互質，第二條則不用
:::

## 質數檢測
### Miller-Rabin Algorithm
1. 有一質數p，一正整數 a < p
如果 $a^2 \bmod p = 1$
則 $a \bmod p = 1$ 或 $a \bmod p = -1 \bmod p = p - 1$
2. p是大於2的質數 則可以寫出 $p - 1 = 2^kq , k>0$ 且$q$為奇數
a 是任意整數 且 $1 < a < p-1$

有以上2點成立則可以知道會符合以下兩條件其中之一
1. $a^q \bmod p = 1$ 或寫成 $a^q \equiv 1(mod p)$.

2. 有一整數j在 1 ≤ j ≤ k 使得:
演算法順序：
:::info
此演算法的結果不一定正確。通過測試的數字，可能是合數或質數；無法通過測試的數字，一定是合數。
:::
雖然通過測試的數不是100%為質數，但假設取了t個值做測試，則有小於(1/4)^t^的機率會誤將和數當成質數
[質數演算法](http://web.ntnu.edu.tw/~algo/Prime.html)

### 中國餘式定理(CRT)

### Discrete Logarithms
primitive root(原根)：
a 和 n 互質 則 當a^1^、a^2^、...、a^Φ(n)^ 都mod n
如果到a^Φ(n)^ mod n 才=1的話，則稱a為n的原根
以上稱2、3、10、13、14、15為mod19的原根(primitive root of the modulus 19)

定義

b ≡ a^i^(mod p)
可以 i = dlog~a,p~(b)表示