RSA算法讲解

感觉经常忘记，所以打算自己记录下，我这里先列个大纲，有时间的话补一下具体的内容

1、裴蜀定理

2、辗转相除法

3、中国剩余定理

以著名的题目《物不知数》来举例，

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

 

我们用数学的语言来表示，就是求同时满足下面三个方程这样的数x

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

 

上面三个方程单独都是有解的，我们来考虑下怎么求这个方程组

我们的思路是，构造这样的数，满足第一个方程，除以3之后余2，同时是5的倍数和7的倍数，也就是说要求这样的方程

35x ≡ 2 (mod 3),  求解后可以得到x=1，也就是说35这个数就满足。

同样的方式来考虑第二个方程，可以得到

21x ≡ 3 (mod 5) ,解得x=3, 也就是说63这个数满足同时是3的倍数和7的倍数，模5之后是余3的

同样考虑第三个方程

15x ≡ 2 (mod 7),解得x=2, 也就是说30这个数满足同时是3的倍数和5的倍数，模5之后是余2的

这样考虑之后，我们得到了三个数分别是35, 63, 30，然后我们把它们加起来得到一个数字是128，注意这个数要拥有的性质

他会同时满足我们上面列的三个方程! 也就是说

128 ≡ 2 (mod 3)

128 ≡ 3 (mod 5)

128 ≡ 2 (mod 7)

原因是因为128 = 35 + 63 + 30

第一个数35满足模3余2，其余两个数都是3的倍数，不影响余数

第一个数63满足模5余3，其余两个数都是5的倍数，不影响余数

第一个数30满足模7余2，其余两个数都是7的倍数，不影响余数

因此加起来之后就得到我们想要的答案，这里注意到，我们把128加上任意的lcm(3, 5, 7) = 105的倍数的值也是满足要求的。

 

因此我们就得到了中国剩余定理的基本形式：(摘自维基百科)

4、费马小定理、欧拉定理

5、RSA算法