互质

两个自然数互质，他们的最大公约数为1 —— 例:(15，32)不一定要是质数
通过互质关系，可以得到以下结论：
　　1. 任意两个质数构成互质关系
　　2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系
　　3. 由2知，如果两个数之中，较大的那个数是质数，则两者构成互质关系
　　4. 1和任意一个自然数是都是互质关系
　　5. p是大于1的整数，则p和p-1构成互质关系，如100和99
　　6. p是大于1的奇数，则p和p-2构成互质关系，如99和97

欧拉函数

目的是求：在小于等于n的正整数之中，有多少个与n构成互质关系？
分类讨论共5种情况：

1. 如果n=1，则：$φ(1) = 1$ 因为1与任何数（包括自身）都构成互质关系。
2. 如果n是质数，则： $φ(n)=n-1$ 因为质数与小于它的每一个数，都构成互质关系。
3. 如果n是质数的某一个次方，即 $n = p^k$ (p为质数，k为大于等于1的整数)，则： $φ(n)=p^k-p^(k-1)=n-n/p$
   比如： $φ(8) = φ(2^3) =2^3-2^2=8-4= 4$
4. 如果n可以分解成两个互质的整数之积，n = p1 × p2则：
   $φ(n) = φ(p1p2) = φ(p1)φ(p2)$ ——by：中国剩余定理
   5.任何一个数都可以写成一系列质数的乘积，故上面四条可解所有数。

欧拉定理 与 费马小定理

若 a ，n互质
欧拉定理：$a^{φ(n)}\equiv1 (mod\ n)$
若 a ， n互质 且n为质数
费马小定理：$a^n\equiv a(mod\ n)$ 即 $a^{n-1}\equiv 1(mod\ n)$

同时当a，n互质时
我们称 $a*b\equiv1(mod\ n)$中的b为a的模反元素（逆元）
ps：费马小定理中：$a^{n-1}\equiv 1(mod\ n)$故可知 a的逆元为$a^{n-2}$

RSA

生成原理

1. 找两个不相等的质数p，q （就是之后因式分解的解）
2. 再设 n=p*q （n密钥组成部分）
   求出$φ(n)=(p-1)*(q-1)$
3. 找到一个数e,要求 1<e<φ(n) 且e与φ(n)互质（e公钥组成部分）
4. 求出e对φ(n)的逆元d（d密钥组成部分）
   $ed\equiv1mod(φ(n))$
   这时候，密钥（d,n）公钥（e,n）就全部生成了

加解密

$密文=明文^e mod n$
$明文=密文^d mod n$

可靠性原理

• 我们知道了 e和n，为了解密，我们需要拿到d
• 可知 $ed\equiv1mod(φ(n))$ 故我们需要拿到φ(n)
• φ(n)=(p-1)*(q-1),但我们不知道p，q所以我们只能对n进行因式分解。
• 应为p，q都是质数，所以n只有p，q一对。但n（1024位！）又很长，因式分解基本不可能实现。（3233=61*53 可以从这个推断一下复杂度——12位2进制）