RSA的例子（二）

上文說了一個RSA的實例，但我說還有很多細節要說，這主要有兩方面的問題，首先就是我跳過了很多嚴謹的數學部份，第二，我也略去了很多實行上的細節．例如，上次我強調，公開鑰和私鑰是可互換的，這是理論．但到實際運作時，我們又會在細節上動腦筋，以增加運算效率！所以，若有人告訴你，公開鑰和私鑰是不可互換的，他並沒有錯．今次，我便和大家先討論一下一些細節．以後，再和大家討論嚴謹的數學部份．

上文的例子在解密時，需要計算17⁷ mod 33，我們計算時，是否真的要把17自乘7次呢？7次事小，實際的數字會大很多很多，怎樣可有效自乘呢？

請想想，(x²)²是甚麼？當然是x⁴，那麼(x⁴)²又等如多少呢？

例如，5¹⁶是可以這樣計算的：

5.5 = 25 （5²）
25.25 = 625 （5⁴）
625.625 = 390625 （5⁸）
390625. 390625 = 152587890625（5¹⁶）

這即是4次乘法便可計算到16次方．但你可能會問，若不是2的級數便不可以了嗎？非也，例如，5¹⁷就是5¹⁶.5即152587890625.5=762939453125
又例如，5¹⁸=5¹⁶.5²

事實上，我們可以有一套很巧妙的算法，就算是很高很高的次方，電腦都可在相對少的運算下計算出來．我為支援太太所寫的書，我就寫了一個簡單的指數計算器（實在是集體創作，我祗是寫了幾句，其他是由我公司的青年人完成的），網址如下

http://www.caconsultant.com/maths/bc_main.php?lang=eng

上文提到我們要先選一個e，這個e是有一定限制的，這限制就是

1 < e < phi, such that gcd(e, phi) = 1

理論上，任何符合上述條件的e都可用，但實際操作時，e都會是下面的3個值中的一個，這就是3, 17或65537(2¹⁶+1）這3個數字都是Fermat Prime，使用它們的其中之一個好處，就是令我們可以方便快捷地計算次方，例如x⁶⁵⁵³⁷=((((x²)²)²)²)².x，6次乘法便可以了！

由於e的選擇祗有3個，所以，必定用來做‘公開鑰’．

使用這3個數還有其他的好處，下文再續．