预备知识：

0. 模运算基本性质

(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

推论： （符号定义，模等：a≡b (% p) <=> a%p = b % p)

若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p);

若a≡b (% p)，则对于任意的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, 将这两个式子带入上面等式的左边，即可求证

1. 互质（coprime）

两个数的最大公因子是1，则这两个数互质

2. 欧拉函数

定义：φ(n) 表示小于n且与n互质的数的个数

欧拉函数：如果p是一个质数，则φ(p^k) = p^k - p^(k-1) = p^k(1-1/p)

证明：
p是大于1的整数，则p和p-1构成互质关系，比如57和56
小于等于p^k的正整数一共p^k个，和p^k不互质的数，一定是p的倍数，他们是 p, 2*p, 3*p, ..... p^(k-1) * p
所以小于等于p^k 与 p^k互质的数，有 p^k - p^(k-1)个

推理：如果p，q是质数，φ(p * q) = φ(p) * φ(q)

证明：网搜中国剩余定理，略

3. 欧拉定理 

欧拉定理: 
    如果两个正整数a和n互质，则n的欧拉函数 φ(n) 满足：a^φ(n) ≡ 1 (mod  n)
  （欧拉函数证明）
费马小定理: 
    a是不能被素数p整除的正整数，则有a^(p-1) ≡ 1 (mod p) => 欧拉定理代进来就可以证明了
个人推理：
    如果两个正整数a和n互质，则n的欧拉函数 φ(n) 满足：a^(k * φ(n)) ≡ 1 (mod  n)
个人推理证明:
a^(k * φ(n)) % p = ((a ^ φ(n) )^k) % p = ((a ^ φ(n) ) % p)^k % p = 1^k % p = 1

欧拉定理的应用的例子：计算 7^222 的个位数
解：
∵ 7 和 10 互质，φ(10) = 4 ∴ 7^4 mod 10 = 1
7^222 % 10 = ((7^4)^55 %10)* (7^2%10) = 7^2 % 10 (参见欧拉定理个人推理) = 9
带入 (a^b) % p = ((a % p)^b) % p， 7^222 = (7^4)^55 mod 

4. 模反元素

定义：
    ab ≡ 1（mod n)，其中a和n互质，则称b为a的对n的模反元素
定理：
    如果a和n互质，则a的模反元素必定存在
证明：
a * a^(φ(n)-1) = a ^ φ(n) ; 根据欧拉定理：a ^ φ(n) ≡ 1（mod n)
那么 a^(φ(n)-1) 就是a对n的模反元素，必然是存在的

RSA原理&过程

秘钥生成过程

1.  p 和 q是两个大素数

2. n = p * q

3. φ(n) = (p-1) * (q-1)  （参见欧拉定理推理）

4. 找一个与φ(n)互质的数e  且1 < e < φ(n) 

5. 找到一个正整数d, d * e ≡ 1（mod φ(n)) （d为e的模反元素）
求解过程: （e的存在性，就是欧拉定理）
d * e - 1 = k * φ(n) => 等效于求解 d * e + k * φ(n) = 1, 其中 e, φ(n) 已知，
因为这个方程是一条直线，可以得到无数个解，能某一种的解法通常能得到一组解

6. 综上，这个时候，公钥和私钥产生了
公钥: (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因数分解，才能算出p和q。=> npc问题

加密过程: (M 明文；C 密文）

1. 将明文内容，适当切割，这样每一段明文能用 0 ~ n-1 的一个整数表示

2. 对于每一段明文M

M^e ≡ C (mod n)： 公钥加密 C = M^e mod n

3. 解密时

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为一个常数
将②代入①，
只需证明
(M^e - k*n)^d ≡ M (mod n)  ②     
根据本文开头同余的定义
(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)  ④

接下来分两种情况:
A. M与N互质
M^(hφ(n)+1) = M^(hφ(n)) * M 根据欧拉定理，M^(hφ(n)) mod n = 1, 得证

B. M与N不互质 (有时间了再推导一下）
因为 N = p * q两个素数的乘积，∴ 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 互质，欧拉定理
∴(kp)^(q-1) ≡ 1 (mod q) 代入⑤有
 (kp)^(h(p-1)(q-1)) * kp ≡ (kp)^(q-1) (mod n)  ≡ (kp)^(p-1) (mod (p*q))