刚开始了解 RSA，先写下流程，深入学习之后再补充吧。
欧拉函数
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？
$$ n = p_1^{k_1}p_2^{k_2}…p_r^{k_r} $$
$$ \phi(x) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_r}) $$
欧拉定理
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
$$ a^{\phi(n)}\equiv1(mod\ n) $$
模反元素
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
$$ ab\equiv1(mod\ n) $$
RSA 加密
- 选择两个不相等的质数 p，q
- 计算乘积 $ n = p * q $
- 计算 n 的欧拉函数 $ \phi(n)=(p-1)(q-1) $
- 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
- 计算e对于φ(n)的模反元素d。使得 $$ ed\equiv1(mod\ \phi(n)) $$
- n，e 是公钥，n，d 是私钥。