【RSA原理2】浅谈

本文是非对称加密算法--RSA算法的第二部分，第一部分主要针对非对称加密算法的背景内容进行了综合的介绍，感兴趣的同学可以自行翻阅查看。

我们知道一个大于1的自然数如果只能被1和他本身整除，那么这个数就叫质数（比如1，2，3，5......）。而两个正整数之间除了1以外，再无其他公因子，我们就称这两个数是互质关系（比如1和4，4和3......），这说明，不是质数也能构成互质关系。由互质关系的性值，我们得出如下性值：

1. 任意两个质数构成互质关系，比如13和61。

2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。

3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。

4. 1和任意一个自然数是都是互质关系，比如1和99。

5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。

6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

知道了互质关系后那么请问，如果任意给定一个正整数n，请问在小于等于n的正整数之中，有多少个数与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）。计算这个值的方法就是欧拉函数，用φ(n)表示。

如果一个个的列举：1，2，3，4，5，6，7，8中只有1，3，5，7与8互质，因此φ(n)=4。那么我们如何列出通用的公式直接求φ(n)呢？接下来我们进一步分析：

①第一种情况

如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。

②第二种情况

如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。

③第三种情况

如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则

比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 - 4 = 4。

这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。

进一步变形得：

由此也能看出【n是质数，则 φ(n)=n-1】是k=1时的特例。

④第四种情况

如果n可以分解成两个互质的整数之积，n = p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)，即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。记住结论就好了。

⑤第五种情况

因为任意一个大于1的正整数，都可以写成一系列质数的积【数论只研究正整数】。

=>

由④可得：

=>

由③可得：

=>

代入化简：

这个就是欧拉函数的一般性公式。因此，想求出一个正整数的欧拉函数首先要进行因数分解，随后带入一般性公式即可求解。

欧拉函数是RSA算法的核心，了解了这个函数后，就可以进行下一步的学习了，欢迎持续关注。