RSA加密解密演算法—數論基礎

本章涉及知識點

1、素數的定義

2、尋找素數演算法—短除法

3、尋找素數演算法—篩選法

4、互質關係

5、歐拉函數的證明

6、歐拉定理

7、費馬小定理

8、模反元素

9、歐幾里得演算法—求最大公約數

10、貝祖定理

11、歐幾里得擴展演算法—求二元一次方程的解

12、大整數快速冪演算法

13、大整數快速冪取模演算法

14、總結

一、素數的定義

質數又稱素數，指在一個大於1的自然數中，除了1和本身之外，無法被其他自然數整除的數

素數具有下列獨特的性質：

（1）素數p的因子有且只有兩個：1和p

（2）素數一定是奇數

（3）任意一個大於1的正整數N，一定可以質因式分解為它的有限個質因子之積

（4）素數的個數是無限的

（5）所有大於10的素數中，其個位數只能是1,3,7,9其中之一

（6）一個充分大的偶數一定可以寫成：一個素數加上一個最多由2個質因子所組成的合成數

如果將素數p表示成極坐標方程

我們將第500到第5000的素數畫在笛卡爾坐標系來觀察其分布：

可以看到素數的分布呈螺旋形狀，這種現象又叫質數螺旋

幾百年之間，無數世界頂級的數學家，研究一生始終無法精確的證明素數的表達式以及其分布的規律

二、尋找素數演算法—短除法

問題定義：在給定範圍n之內，找到所有素數

（1）方法一：

最直接的方法就是從定義出發，對於任意整數p，用[2，p-1]去整除p，如果發現p可以被整除，p就不是素數

顯然，這個方法的效率簡直低的讓人難以接受，優化空間非常大

（2）方法二：

顯然偶數不是素數，對於任意奇數p，用[3，5，...，p-2]去整除p，如果發現p可以被整除，p就不是素數

這個方法的效率稍微高了一些，但是其本質和方法一沒有任何區別，只是整除係數範圍縮小到奇數

（3）方法三：

利用質因式分解的思想，對於任意奇數p，用小於p的素數去整除p，如果發現p可以被整除，p就不是素數

這個方法的計算效率又提高了一些，將奇數級別的除數縮小到質數範圍

（4）方法四：

利用平方根條件，對於任意奇數p，用小於p的平方根的素數去整除p，如果發現p可以被整除，p就不是素數

這個方法將素數級別的除數又縮小到不大於其平方根的範圍，我們稱之為短除法

我們用python實現短除演算法，並測試尋找在[2，2^22]範圍內所有的素數的演算法效率

耗時為

從短除演算法尋找結果中，可以看到該演算法花費了13秒，找到295947個素數

三、尋找素數演算法—篩選法

除了上述的短除演算法，是否存在更加高效的演算法來尋找素數？

的確存在一個非常高效的演算法—篩選法，其設計思想是：

（1）將n個數字全部放進數組，並都置為肯定狀態

（2）將數組下標是偶數的數字全部置為否定狀態

（3）依次遍曆數組長度的平方根個數字

（4）如果當前數字處於被肯定的狀態，則將其倍數的數字狀態置為否定

我們用python實現篩選演算法，並測試尋找在[2，2^22]範圍內所有的素數的演算法效率

耗時為

從篩選演算法尋找結果中，可以看到該演算法只花費了1.16秒，就找到295947個素數

至此我們可以總結出比較上述找尋素數的兩種演算法

（1）短除演算法：使用了嚴進寬出的思想，對每個數字的判斷非常嚴格，保證每次找到的數字都是素數，時間複雜度較高

（2）篩選演算法：使用了寬進嚴出的思想，一步步篩選（否定），最後保留下來的數字才是素數，利用空間換取時間來大大降低了時間複雜度

四、互質關係

公因數只有1的兩個數字，稱為互質關係

互質具有下列獨特的性質：

（1）任意兩個素數一定是互質關係

（2）如果一個數是素數，另一個數字不是它的倍數，則二者互質

（3）較大的數是素數，則二者互質

（4）相鄰的兩個自然數一定互質

（5）相鄰的兩個奇數一定互質

（6）1和任意數互質

五、歐拉函數的證明

問題的提出：

給定任意正整數n，問在小於等於n的正整數之中，有多少個數字與n構成互質關係？

我們定義歐拉函數φ(n)來表示這個值，則分析討論φ(n)可能存在的情況

（1）當n等於1的情況：

則根據互質的性質6可以得到

（2）當n等於素數p的情況：

則n以下的數字和n都互質

（3）當n等於素數的某一個次方，即n = p^k的情況：

則小於等於p^k且與p^k不互質的個數有

則φ(n) = （p^k個數字） - （小於等於p^k且與p^k不互質的個數），即

（4）當n等於兩個素數的乘積，即n=p*q（p和q互質）的情況：

則φ(n) =φ(pq)滿足乘法分配律，即

（5）當n等於任意大於1的正整數的情況：

由素數的性質3（質因數分解）可以得到

其中p1、p2...pr都是n的質因數

則根據上述(3)和(4)的分析結果，可以推導出

綜上分析，我們得到歐拉函數的通用計算方式為

六、歐拉定理

歐拉定理是解決同餘的性質，其定義為：

如果p和q為正整數，且pq互質，則

顯然，我們可以用歐拉函數來判斷兩個正整數是否互質

七、費馬小定理

費馬小定理是歐拉定理的特殊情況，其定義為：

如果p和q為正整數，且pq互質，且q是素數，則q的歐拉函數為

則歐拉定理可以寫為

八、模反元素的定義

模反元素指：如果兩個正整數p和q互質，那麼一定存在一個或多個整數b，使得

我們可以通過歐拉函數的定義來證明模反元素的必然存在

可以看到p的φ(n) -1次方就是p的一個模反元素

九、歐幾里得演算法—求最大公約數

問題提出：計算兩個正整數a和b的最大公約數？

歐幾里得演算法，又稱輾轉相除法，其定義最大公約數滿足：

下面我們來證明該演算法

設a>b>1，則

其中k為a除以b的商，r為a對b取模，即

設d是a和b的一個公因數，則d可以整除a和b，即

又因為r = a - kb，則

可以看到d也可以整除r，即

綜上，我們可以證明出

十、貝祖定理

貝祖定理是初等數論里提出的一個定理，它的定義為：

如果有兩個正整數a和b，則存在若干整數對x，y，使得

該定理說明：a和b的最大公約數滿足a和b的線性組合

其中當gcd(a,b)=1時，則證明a和b都是素數，即

十一、歐幾里得擴展演算法

歐幾里得擴展演算法是用來求解出貝祖等式ax+by=gcd(a，b)的一個解(x，y)，即求解二元一次線性方程

演算法證明：

令

則c可以表示為商q和餘數r的線性形式

我們已知線性方程組為

將c帶入第一個方程，得到

將d的表達式帶入上式，得到

下面我們將參數表做如下變化

經過上述變化，將參數變化帶入化簡2，得到

將參數變化帶入線性方程組的第二個方程，得到

綜上所述，可以看到線性方程組經過參數表的變化後，保持了原線性方程組的正確性

至此，我們總結出歐幾里得擴展演算法的步驟為：

（1）初始化參數：x" = y = 1，x = y" = 0，c = a，d = b

（2）令q和r表示d除以c得到的商和餘數

（3）如果餘數r不為0，則進入循環，按照變化參數列表更新參數，返回第(2)步

（4）如果餘數r為0，則演算法終止，返回x和y即為所求

我們用python實現歐幾里得擴展演算法，並測試求解：47x + 30y = 1的解？

計算結果為

可以看到x=-7，y=11，帶入到方程計算得-7*47+30*11=1，確實是該二元方程的一組整數解

十二、大整數快速冪演算法

如果我們要計算a的11次方，則按照冪運算的定義，需要執行11次乘法

如果將指數11寫成二進位，則

可以看到經過上述變化，計算a的11次方只需要執行3次乘法即可，這就是快速冪演算法的原理

快速冪演算法步驟為：

（1）將冪指數視為二進位進入循環

（2）判斷指數二進位權位是否為奇數，如果為奇數，則累乘結果

（3）每次循環對指數進行左移位運算，以及對底數進行累乘運算

比較快速冪演算法和直接連乘法的效率

可以看到，快速冪演算法的效率非常高

十三、大整數快速冪取模演算法

快速冪取模演算法基於下面這個取模等價式子

它的思路和快速冪演算法一致，在循環過程加入取模運算即可

比較快速冪取模演算法和直接連乘取模的效率

可以看到，加入取模計算後，快速冪取模演算法幾乎是瞬間完成計算

至此，有了上述數論的基礎知識和相應的演算法，將這些數學理論和演算法串聯，我們就可以開始RSA演算法的實戰

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！