【RSA原理3】浅谈--什么是欧拉定理

在第2章中讲到了欧拉函数，我们可以只要能将一个正整数分解成若干数的乘积，就能快速计算一个正整数的欧拉函数值，其实欧拉函数的作用更多的是体现在欧拉定理上。那么欧拉定理又是什么呢？

目录

1.欧拉定理

2.费马小定理

3.总结

1.欧拉定理

如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：

也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。欧拉定理可以大大简化某些运算。比如，7和10互质，根据欧拉定理：

由于：

=>

已知 φ(10) 等于4，所以马上得到7的4倍数次方的个位数肯定是1。

因此，7的任意次方的个位数（例如7的222次方），心算就可以算出来应该得9。

 进一步展开：

 计算7的平方：

因此7的222次方个位数就是1*1*9=9.

2.费马小定理

欧拉定理有一个特殊情况。假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成:

这就是著名的费马小定理。它是欧拉定理的特例。

3.总结

欧拉定理是RSA算法的核心。理解了这个定理，就可以理解RSA了，后续我将尽可能用通俗易懂的方法对RSA进行论述。