預(yù)備知識(shí)：
0. 模運(yùn)算基本性質(zhì)
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a^b) % p = ((a % p)^b) % p
推論： （符號(hào)定義，模等：a≡b (% p) <=> a%p = b % p)
若a≡b (% p)，則對(duì)于任意的c，都有(a + c) ≡ (b + c) (%p);
若a≡b (% p)，則對(duì)于任意的c，都有(a * c) ≡ (b * c) (%p);?
若a≡b (% p)，c≡d (% p)，則 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)， (a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)；
證明方法: a = k1*p + a%p; b = k2*p + b % p, 將這兩個(gè)式子帶入上面等式的左邊，即可求證
1. 互質(zhì)（coprime）
兩個(gè)數(shù)的最大公因子是1，則這兩個(gè)數(shù)互質(zhì)
2. 歐拉函數(shù)
定義：φ(n) 表示小于n且與n互質(zhì)的數(shù)的個(gè)數(shù)
歐拉函數(shù)：如果p是一個(gè)質(zhì)數(shù)，則φ(p^k) = p^k - p^(k-1) = p^k(1-1/p)
證明：
p是大于1的整數(shù)，則p和p-1構(gòu)成互質(zhì)關(guān)系，比如57和56
小于等于p^k的正整數(shù)一共p^k個(gè)，和p^k不互質(zhì)的數(shù)，一定是p的倍數(shù)，他們是 p, 2*p, 3*p, ..... p^(k-1) * p
所以小于等于p^k 與 p^k互質(zhì)的數(shù)，有 p^k - p^(k-1)個(gè)
推理：如果p，q是質(zhì)數(shù)，φ(p * q) = φ(p) * φ(q)
證明：網(wǎng)搜中國(guó)剩余定理，略
3. 歐拉定理?
歐拉定理:?
? ? 如果兩個(gè)正整數(shù)a和n互質(zhì)，則n的歐拉函數(shù) φ(n) 滿足：a^φ(n) ≡ 1 (mod? n)
? （歐拉函數(shù)證明）
費(fèi)馬小定理:?
? ? a是不能被素?cái)?shù)p整除的正整數(shù)，則有a^(p-1) ≡ 1 (mod p) => 歐拉定理代進(jìn)來(lái)就可以證明了
個(gè)人推理：
? ? 如果兩個(gè)正整數(shù)a和n互質(zhì)，則n的歐拉函數(shù) φ(n) 滿足：a^(k * φ(n))?≡ 1 (mod? n)
個(gè)人推理證明:
a^(k * φ(n)) % p = ((a ^ φ(n) )^k) % p = ((a ^ φ(n) ) % p)^k % p = 1^k % p = 1
歐拉定理的應(yīng)用的例子：計(jì)算 7^222 的個(gè)位數(shù)
解：
∵ 7 和 10 互質(zhì)，φ(10) = 4 ∴ 7^4 mod 10 = 1
7^222 % 10 = ((7^4)^55 %10)* (7^2%10) = 7^2 % 10 (參見歐拉定理個(gè)人推理) = 9
帶入 (a^b) % p = ((a % p)^b) % p， 7^222 = (7^4)^55 mod?
4. 模反元素
定義：
? ? ab?≡ 1（mod n)，其中a和n互質(zhì)，則稱b為a的對(duì)n的模反元素
定理：
? ? 如果a和n互質(zhì)，則a的模反元素必定存在
證明：
a * a^(φ(n)-1) = a ^ φ(n) ; 根據(jù)歐拉定理：a ^ φ(n)?≡ 1（mod n)
那么?a^(φ(n)-1) 就是a對(duì)n的模反元素，必然是存在的
RSA原理&過(guò)程
秘鑰生成過(guò)程
1. ?p 和 q是兩個(gè)大素?cái)?shù)
2. n = p * q
3. φ(n) = (p-1) * (q-1)? （參見歐拉定理推理）
4.?找一個(gè)與φ(n)互質(zhì)的數(shù)e ?且1 < e < φ(n)?
5. 找到一個(gè)正整數(shù)d, d * e ≡ 1（mod φ(n)) （d為e的模反元素）
求解過(guò)程: （e的存在性，就是歐拉定理）
d * e - 1 = k * φ(n) => 等效于求解 d * e + k * φ(n) = 1, 其中 e, φ(n) 已知，
因?yàn)檫@個(gè)方程是一條直線，可以得到無(wú)數(shù)個(gè)解，能某一種的解法通常能得到一組解
6. 綜上，這個(gè)時(shí)候，公鑰和私鑰產(chǎn)生了
公鑰: (e, n)
私鑰：(d, n)
安全性證明
（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有將n因數(shù)分解，才能算出p和q。=> npc問題
加密過(guò)程: (M 明文；C 密文）
1. 將明文內(nèi)容，適當(dāng)切割，這樣每一段明文能用 0 ~ n-1 的一個(gè)整數(shù)表示
2. 對(duì)于每一段明文M
M^e?≡ C (mod n)： 公鑰加密 C = M^e mod n
3. 解密時(shí)
C^d?≡ M (mod n)：私鑰解密 M = C^d mod n
加密和解密的證明
要證明?C^d?≡ M (mod n) ①
∵ M^e?≡ C (mod n)? ∴ C = M^e - kn ②；k為一個(gè)常數(shù)
將②代入①，
只需證明
(M^e - k*n)^d?≡ M (mod n)? ②? ? ?
根據(jù)本文開頭同余的定義
(M^e - k*n)^d % n =?(M^e%n - k*n%n)^d % n = (M^e%n)^d%n =? M^(ed) %n
所以要證明②，只需證明
?M^(ed)?≡?M (mod n) ③
∵?ed ≡ 1 (mod φ(n))? ∴?ed = hφ(n)+1, 代入 ③得到，只需證明
?M^(hφ(n)+1)?≡M (mod n)? ④
接下來(lái)分兩種情況:
A. M與N互質(zhì)
M^(hφ(n)+1) =?M^(hφ(n)) * M 根據(jù)歐拉定理，M^(hφ(n)) mod n = 1, 得證
B. M與N不互質(zhì) (有時(shí)間了再推導(dǎo)一下）因?yàn)?N = p * q兩個(gè)素?cái)?shù)的乘積，∴ M = kp or M = kq，只需證明M=kp的情況，代入M = kp, 有：
M^(hφ(n)+1) = （kp) ^ (hφ(n)+1) = (kp)^(h(p-1)(q-1)) * kp ⑤
∵ (kp)^φ(q)??≡ 1 (mod q) …… p,q 互質(zhì)，歐拉定理
∴(kp)^(q-1)?≡ 1 (mod q) 代入⑤有
?(kp)^(h(p-1)(q-1)) * kp?≡ (kp)^(q-1) (mod n)??≡ (kp)^(p-1) (mod (p*q))?
