欧拉函数
欧拉函数的定义
在数论中，对正整数n，欧拉函数 $\phi$ 是 小于等于n的正整数中 与n互质的数的个数。
如果两个或两个以上的整数的最大公因数是 1 ，则称它们为互质。
例如，小于等于6的正整数中，有1和5两个数与6互质，因此 $\phi(6)=2$。
欧拉函数的一些性质
1.
质数（素数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
特别的，由定义得出，令p为质数，则小于p的任意正整数都与它互质，得出 $\phi(p)=p-1$
2.
令p为质数，则$\phi(p^{m})=(p-1) \times p^{m-1}$，证明过程如下：
直接正推比较困难，由此我们便可以使用容斥原理的思想，小于等于$p^{m}$的正整数共有$p^{m}$个，用$p^{m}$减去与其中它不互质的正整数的个数，便可以得到 $\phi(p^{m})$。
那么，从1到$p^{m}$的正整数中，有哪些数是与$p^{m}$不互质的呢？
显然只有$p$的倍数与其不互质（最大公因数为$p$），即有 $p,p \times 2,p \times 3,\cdots,p \times p^{m-1}$ 这 $p^{m-1}$ 个数，
由此，我们可以得出，$\phi(p^{m})=p^{m}-p^{m-1}=(p-1) \times p^{m-1}$
3.
对于任意正整数，欧拉函数的通式为 $\phi(n)=n\times \prod_{质数p_i|n}(1-\frac{1}{p_i})$，证明过程如下：
由正整数的唯一分解定理（算术基本定理），任意一个正整数都能被表示成若干个质数的乘积，且表示方法是唯一的。
即 $n=p_1^{m1}p_2^{m2}\cdots p_m^{mm}\quad n\in N^{*}$
再根据容斥原理，我们假设正整数$n$有两个质因子 $p_1,p_2$，那么这两个质因子的倍数都与$n$不互质，我们需要减去这两个质因子的倍数的个数，但请注意，这两个质因子乘积的倍数（公倍数）的个数相当于被减了两次，故还需再加上一次。
即$n-\frac{n}{p_1}-\frac{n}{p_2}+\frac{n}{p_1 \times p_2}=n(1-\frac{1}{p_1}-\frac{1}{p_2}+\frac{1}{p_1 \times p_2})=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})$
那么再进一步，$\phi(n)$ 就等于1减去构成$n$的各种质因子（即1到$n$满足能整除$n$的质数）的倒数的差的累乘。
当$n$为质数时，$\phi(n)=n\times (1-\frac{1}{n})=n-1$，恰好就是我们得出的上一条结论。
4.
假设有两个互质的正整数$n,m$，则$\phi(nm)=\phi(n)\phi(m)$，证明如下：
由欧拉函数通式得：
$\phi(n) \phi(m)=$$n \times \prod(1 - \frac{1}{p_i}) \times m \times \prod(1 - \frac{1}{p_j})$
由于两数互质，不会存在公共的质因子，因此两个累乘实际可以合并，进一步化简：
$=nm \times \prod(1 - \frac{1}{p_k})=\phi(nm)$
因此，欧拉函数是一个积性函数。
RSA算法
背景
在20世纪70年代之前，只存在传统的对称加密算法，即加密和解密采用同一种规则，且加密和解密所用密钥相同，安全地传递密钥就成为了一个大问题。
而RSA就是一种新型的非对称加密算法，这种算法可以生成公钥和私钥两把钥匙，公钥是公开的，而私钥是保密的，用一把钥匙加密的信息要用另一把钥匙来解密。如此一来，只要私钥不泄漏，就能保证通信是安全的。
实现原理
欧拉定理
如果两个正整数$a$和$n$互质，则 $a^{\phi(n)} \equiv 1 \pmod n$
也就是说，a的 $\phi(n)$ 次方模n的余数为1，可以表示为$a^{\phi(n)}-1=kn \quad k\in N$。
举个例子，3与7互质，那么$7^{\phi(3)}-1=7^2-1=48=16 \times 3$
欧拉定理的证明需要使用到群论知识，这里就不再介绍，记住结论即可。
特别的，当$n$为质数时，得到$a^{n-1} \equiv 1 \pmod n$，这就是著名的费马小定理，可见是欧拉定理的特殊情况。
模反元素
如果有$e,r$两个数互质，那么一定存在整数 $d$ 使 $ed \equiv 1 \pmod r$，这时 $d$ 就叫做 $e$ 的模反元素。
由欧拉定理 $e^{\phi(r)}=e \times e^{\phi(r)-1} \equiv 1 \pmod r$可见，必然存在$e$的模反元素 $e^{\phi(r)-1}$。
密钥生成
1.选择两个不同质数
实际应用中，选择的这两个质数$p_1,p_2$越大，破解难度就越大。
2.计算两数乘积
计算出这两个质数的乘积，记作$n$。
则$r=\phi(n)=\phi(p_1)\phi(p_2)=(p_1-1)(p_2-1)$
3.随机选取e
在开区间 $(1, \phi(n))$ 中随机选取一个与$r$互质的整数$e$。（实际应用中常用65537）
4.求模反元素d
计算$e$关于$r$的模反元素$d$，即解方程$ed-1=kr \quad k\in N$（可使用exgcd扩展欧几里得算法求出解）。
5.封装公钥和私钥
在RSA加密算法中，公钥为二元组(n,e)，私钥为(n,d)。
实际应用中的密钥格式符合ASN.1标准。
生成密钥后，选取的 $p_1,p_2$ 即可销毁。
加密和解密
使用公钥加密
假设我们有一个整数$m \quad (m<n)$需要加密（实际使用时字符串可以编码成数字）。
那么我们就需要计算满足以下条件的整数$c$：
$m^e \equiv c \pmod n$
$c$即为加密后的结果
使用私钥解密
得到密文$c$后，计算满足以下条件的整数$m$：
$c^d \equiv m \pmod n$
$m$即为解密后的原文，因为$m<n$，所以解密结果唯一。
大数据的加密
待加密的整数$m$存在小于$n$的约束条件，那么在$m$非常大的情况下，我们就可以采用分段加密的方式，或是使用对称加密加密，再用RSA加密对称加密的密钥，也能保证其安全性。
解密可行性证明
最后我们解决一个问题，为什么这样就能实现数据的加密和还原？
也就是证明加密时的$m$也能满足解密时的同余方程。
根据
$m^e \equiv c \pmod n$
转化为
$c=m^e-kn \quad k\in N$
要证明式子 $c^d \equiv m \pmod n$
就要证明 $(m^e-kn)^d \equiv m \pmod n$
即 $m^{ed} \equiv m \pmod n$
$m^{ed-1} \equiv 1 \pmod n$
因为 $ed=zr+1 \quad z\in N$
所以 $m^{ed-1}=m^{zr+1-1}=m^{z \phi(n)}={m^{\phi(n)}}^z$
最终我们得到，这个问题转化为证明 $m^{\phi(n)} \equiv 1 \pmod n$
接下来分类讨论：
- 当$m$和$n$互质时，这个式子由欧拉定理显然成立。
- 当$m$和$n$不互质时，因为$n=p_1 \times p_2$，同时$m<n$，所以$m=kp_1$或$m=kp_2$。
假设$m=kp_1$，因为$m<n$，所以$k<p_2$，$k$与$p_2$互质，$kp_1$与$p_2$互质，
由欧拉定理，${(kp_1)}^{\phi(p_2)} \equiv 1 \pmod {p_2}$，
即${(kp_1)}^{p_2-1} \equiv 1 \pmod {p_2}$
${[(kp_1)}^{p_2-1}]^{z(p_1-1)} \times kp_1 \equiv kp_1 \pmod {p_2}$
${(kp_1)}^{ed} \equiv kp_1 \pmod {p_2}$
则 ${(kp_1)}^{ed}=kp_1+lp_2$
因为$p_1|l,n=p_1p_2$，所以$m^{ed}\equiv m \pmod {n}$
证明原式成立。
$m=kp_2$时同理。
安全性
如果要从公钥中的 $e$ 推出私钥 $d$，那就必须要知道 $\phi(n)$，就必须要将 $n$ 质因数分解成 $p_1,p_2$ 或从1开始枚举个数，在 $n$ 的位数极其庞大时，要想计算出来几乎是不可能的。
这意味着RSA算法十分可靠，密钥越长就约难以破解。目前公开破译的位数是768位，而实际使用一般是1024位或是2048位，所以理论上极其安全。
