三公演算法

① 已知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的最大公約數