1、欧拉函数ϕ

1.1、互质关系

如果两个正整数，除以1以外，没有其他公因数，我们就称这两个树是互质关系。

1.2、欧拉函数的特点

1、当n是质数的时候ϕ(n) = n -1.
2、如果n可以分解为两个互质的整数之积，例如：
n = A * B则：
ϕ(A * B)= ϕ(A) * ϕ(B)
根据以上特点得到：
如果N是两个质数P1和P2的乘积则：ϕ(N)=ϕ(P1) * ϕ(P2)=(P1-1)*(P2-2);
例如：
8的欧拉函数，和8互质的1、3、5、7，ϕ(8)=4
7的欧拉函数，和7互质的1、2、3、4、5、6，ϕ(7)=6
ϕ(56)=ϕ(8) * ϕ(7) = 4 * 6 = 24

1.3、欧拉定理

1、欧拉定理
如果两个正整数m和n互质，那么m的ϕ(n)次方减去1，可以被n整除。

欧拉定理

2、费马小定理
欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么ϕ(n)的结果就是n-1

费马小定理
3、公式推导
公式推导
模反元素

如果两个正整数e和x互质，那么一定可以找到正整数d，使得ed-1被x整除。那么d就是e对于x的模反元素。

模反元素

1.4、迪菲赫尔曼秘钥交换

秘钥交换

原理：

原理

最终推导结果

加密-解密

1.5、RSA算法

1、关于RSA的安全：
除了公钥用到了n和e，其余的4个数字是不公开的。
破解RSA得到d的方式如下：
1）、要想求出私钥d。由于e*d=ϕ(n) * k + 1。要知道e和ϕ(n)
2）、e是知道的，但是要得到ϕ(n)，必须知道p1和p2。
3）、由于n =p1 * p2。只有将n因数分解才能算出。