三公算法

① 已知RSA算法中，素数p=5,q=7,模数n=35,公开密钥e=5,密文c=10，求明文

密钥d=5

明文m=c的d次方mod n

m=100000mod35

=5

或

解密密钥：{d，n}={d，35}，

密文：C=10，

选择两个素数：p=5,q=7，则n=35=5*7。

计算φ(p-1)(q-1)=(5-)(7-1)=24，在[0，23]中选择一个和24互素的数，本题选e=5，得5*d=l mod 24，解出d。不难得出，d=5，因为e×d = 5×5 = 25 = 1*24+1=1 mod 24。

因为：m=Cd(mod n)

所以，m=Cd(mod n)=5。

(1)三公算法扩展阅读：

当公钥e取较小的值，虽然会使加密变得易于实现，速度有所提高，但这样做也是不安全的。最简单的办法就是e和d都取较大的值。

因为密钥的产生受素数产生技术的限制，所以也有它的局限性。

（1）密钥的产生受素数产生技术的限制，因而难以做到一次一密。

（2）分组长度太大，为保证安全性，n至少也要600比特以上，使运算代价很高，尤其是速度较慢，比对称密码算法慢几个数量级；随着大整数素因数分解算法的改进和计算机计算能力的提高，对n的长度在不断增加，不利于实现数据格式的标准化。

② 3个数最大公约数算法

对于3个数A，B，C，最小公倍数=A*B*C/最小公约数的平方
对于对小公约数，可以采用两次辗转相除法
先求A，B的最小公约数D
再求出C与D的最小公约数E
那么E就是这三个数的最小公约数
A*B*C/E/E就是三个数的最小公倍数

举例如下
求1734,816和1343的最大公约数：
首先求1734,816的最大公约数：
gcd(1734,816)表示开始求1734,816的最大公约数。

gcd(1734,816)
=gcd(1734,816)1734=2*816+102
（102为1734除以816的余数，而2为商，以后的如此类推）
=gcd(816，102)816=8*102
（至此余数为0，则102为1734和816的最大公约数）
运用3个数的最大公约数的求解原理：

只需求的1343和102的最大公约数即为1734,816和1343的最大公约数。

gcd(1343，102)
=gcd(1343，102)1343=13*102+17
=gcd(102，17)102=6*17
（至此余数为0，则17为即为1734,816和1343的最大公约数）

则17为即为1734,816和1343的最大公约数

更相减损术求解（也是现学现卖的）

原理：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法，实际上就是辗转相除法。

首先看1734和816.
两个数都是偶数，为了简化计算，都除以2得到867和408.
下面是计算过程：
867-408=459
459-408=51
408-51=357
357-51=306
306-51=255
255-51=204
204-51=153
153-51=102
102-51=51
至此所得的减数和差相等，由于867和408是1734和816除以2得到的数字。故
1734和816的最大公约数还是102（51*2=102）.
在用更相减损术求102和1343的的最大公约数即为1734,816和1343的最大公约数。
1343-102=1241(由于102*10=1020,1343-1020=323,323还是大于102的）
...
...
...
323-102=221
221-102=119
119-102=17
102-17=85
85-17=68
68-17=51
51-17=34
34-17=17
至此所得的减数和差相等.故17为1734,816和1343的最大公约数