本章涉及知識點

1、素數(shù)的定義

2挚币、尋找素數(shù)算法—短除法

3蕊退、尋找素數(shù)算法—篩選法

4假残、互質(zhì)關(guān)系

5架谎、歐拉函數(shù)的證明

6漾脂、歐拉定理

7筐乳、費馬小定理

8争占、模反元素

9恃泪、歐幾里得算法—求最大公約數(shù)

10队腐、貝祖定理

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

12薪前、大整數(shù)快速冪算法

13润努、大整數(shù)快速冪取模算法

14、總結(jié)

一示括、素數(shù)的定義

質(zhì)數(shù)又稱素數(shù)铺浇，指在一個大于1的自然數(shù)中，除了1和本身之外垛膝，無法被其他自然數(shù)整除的數(shù)

素數(shù)具有下列獨特的性質(zhì)：

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

（2）素數(shù)一定是奇數(shù)

（3）任意一個大于1的正整數(shù)N鳍侣，一定可以質(zhì)因式分解為它的有限個質(zhì)因子之積

（4）素數(shù)的個數(shù)是無限的

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

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

如果將素數(shù)p表示成極坐標(biāo)方程

素數(shù)p的極坐標(biāo)方程

我們將第500到第5000的素數(shù)畫在笛卡爾坐標(biāo)系來觀察其分布：

素數(shù)螺旋

可以看到素數(shù)的分布呈螺旋形狀吼拥，這種現(xiàn)象又叫質(zhì)數(shù)螺旋

幾百年之間倚聚，無數(shù)世界頂級的數(shù)學(xué)家，研究一生始終無法精確的證明素數(shù)的表達(dá)式以及其分布的規(guī)律

二凿可、尋找素數(shù)算法—短除法

問題定義：在給定范圍n之內(nèi)惑折，找到所有素數(shù)

（1）方法一：

最直接的方法就是從定義出發(fā)，對于任意整數(shù)p枯跑，用[2惨驶，p-1]去整除p，如果發(fā)現(xiàn)p可以被整除全肮，p就不是素數(shù)

顯然敞咧，這個方法的效率簡直低的讓人難以接受，優(yōu)化空間非常大

（2）方法二：

顯然偶數(shù)不是素數(shù)辜腺，對于任意奇數(shù)p休建，用[3，5评疗，...测砂，p-2]去整除p，如果發(fā)現(xiàn)p可以被整除百匆，p就不是素數(shù)

這個方法的效率稍微高了一些砌些，但是其本質(zhì)和方法一沒有任何區(qū)別，只是整除系數(shù)范圍縮小到奇數(shù)

（3）方法三：

利用質(zhì)因式分解的思想加匈，對于任意奇數(shù)p存璃，用小于p的素數(shù)去整除p，如果發(fā)現(xiàn)p可以被整除雕拼，p就不是素數(shù)

這個方法的計算效率又提高了一些纵东，將奇數(shù)級別的除數(shù)縮小到質(zhì)數(shù)范圍

（4）方法四：

利用平方根條件，對于任意奇數(shù)p啥寇，用小于p的平方根的素數(shù)去整除p偎球，如果發(fā)現(xiàn)p可以被整除洒扎，p就不是素數(shù)

這個方法將素數(shù)級別的除數(shù)又縮小到不大于其平方根的范圍，我們稱之為短除法

我們用python實現(xiàn)短除算法衰絮，并測試尋找在[2袍冷，2^22]范圍內(nèi)所有的素數(shù)的算法效率

短除算法

尋找結(jié)果

從短除算法尋找結(jié)果中，可以看到該算法花費了13秒猫牡，找到295947個素數(shù)

三胡诗、尋找素數(shù)算法—篩選法

除了上述的短除算法，是否存在更加高效的算法來尋找素數(shù)镊掖？

的確存在一個非常高效的算法—篩選法乃戈，其設(shè)計思想是：

（1）將n個數(shù)字全部放進(jìn)數(shù)組，并都置為肯定狀態(tài)

（2）將數(shù)組下標(biāo)是偶數(shù)的數(shù)字全部置為否定狀態(tài)

（3）依次遍歷數(shù)組長度的平方根個數(shù)字

（4）如果當(dāng)前數(shù)字處于被肯定的狀態(tài)亩进，則將其倍數(shù)的數(shù)字狀態(tài)置為否定

我們用python實現(xiàn)篩選算法症虑，并測試尋找在[2，2^22]范圍內(nèi)所有的素數(shù)的算法效率

篩選算法

尋找結(jié)果

從篩選算法尋找結(jié)果中归薛，可以看到該算法只花費了1.16秒谍憔，就找到295947個素數(shù)

至此我們可以總結(jié)出比較上述找尋素數(shù)的兩種算法

（1）短除算法：使用了嚴(yán)進(jìn)寬出的思想，對每個數(shù)字的判斷非常嚴(yán)格主籍，保證每次找到的數(shù)字都是素數(shù)习贫，時間復(fù)雜度較高

（2）篩選算法：使用了寬進(jìn)嚴(yán)出的思想，一步步篩選（否定）千元，最后保留下來的數(shù)字才是素數(shù)苫昌，利用空間換取時間來大大降低了時間復(fù)雜度

四、互質(zhì)關(guān)系

公因數(shù)只有1的兩個數(shù)字幸海，稱為互質(zhì)關(guān)系

互質(zhì)具有下列獨特的性質(zhì)：

（1）任意兩個素數(shù)一定是互質(zhì)關(guān)系

（2）如果一個數(shù)是素數(shù)祟身，另一個數(shù)字不是它的倍數(shù)，則二者互質(zhì)

（3）較大的數(shù)是素數(shù)物独，則二者互質(zhì)

（4）相鄰的兩個自然數(shù)一定互質(zhì)

（5）相鄰的兩個奇數(shù)一定互質(zhì)

（6）1和任意數(shù)互質(zhì)

五袜硫、歐拉函數(shù)的證明

問題的提出：

給定任意正整數(shù)n，問在小于等于n的正整數(shù)之中挡篓，有多少個數(shù)字與n構(gòu)成互質(zhì)關(guān)系婉陷？

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

（1）當(dāng)n等于1的情況：

則根據(jù)互質(zhì)的性質(zhì)6可以得到

n=1的情況

（2）當(dāng)n等于素數(shù)p的情況：

則n以下的數(shù)字和n都互質(zhì)

n=p的情況

（3）當(dāng)n等于素數(shù)的某一個次方官研，即n = p^k的情況：

則小于等于p^k且與p^k不互質(zhì)的個數(shù)有

小于等于p^k且與p^k不互質(zhì)的個數(shù)

則φ(n) = （p^k個數(shù)字） -? （小于等于p^k且與p^k不互質(zhì)的個數(shù)）秽澳，即

n=p^k的情況

（4）當(dāng)n等于兩個素數(shù)的乘積，即n=p*q（p和q互質(zhì)）的情況：

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

n=p*q的情況

（5）當(dāng)n等于任意大于1的正整數(shù)的情況：

由素數(shù)的性質(zhì)3（質(zhì)因數(shù)分解）可以得到

正整數(shù)n的質(zhì)因數(shù)分解

其中p1担神、p2...pr都是n的質(zhì)因數(shù)

則根據(jù)上述(3)和(4)的分析結(jié)果，可以推導(dǎo)出

n等于任意大于1的正整數(shù)的情況

綜上分析蛛壳，我們得到歐拉函數(shù)的通用計算方式為

歐拉函數(shù)的通用計算方式

六杏瞻、歐拉定理

歐拉定理是解決同余的性質(zhì)，其定義為：

如果p和q為正整數(shù)衙荐，且pq互質(zhì)捞挥，則

歐拉定理

顯然，我們可以用歐拉函數(shù)來判斷兩個正整數(shù)是否互質(zhì)

七忧吟、費馬小定理

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

如果p和q為正整數(shù)，且pq互質(zhì)溜族，且q是素數(shù)讹俊，則q的歐拉函數(shù)為

q的歐拉函數(shù)

則歐拉定理可以寫為

費馬小定理

八、模反元素的定義

模反元素指：如果兩個正整數(shù)p和q互質(zhì)煌抒，那么一定存在一個或多個整數(shù)b仍劈，使得

模反元素

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

明模反元素的必然存在

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

九、歐幾里得算法—求最大公約數(shù)

問題提出：計算兩個正整數(shù)a和b的最大公約數(shù)寡壮？

歐幾里得算法贩疙，又稱輾轉(zhuǎn)相除法，其定義最大公約數(shù)滿足：

歐幾里得算法

下面我們來證明該算法

設(shè)a>b>1况既，則

商和余數(shù)的形式

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

商和余數(shù)

設(shè)d是a和b的一個公因數(shù)棒仍，則d可以整除a和b悲靴，即

d可以整除a和b

又因為r = a - kb，則

d可以整除r

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

d可以整除r

綜上癞尚，我們可以證明出

歐幾里得算法

十、貝祖定理

貝祖定理是初等數(shù)論里提出的一個定理榜配，它的定義為：

如果有兩個正整數(shù)a和b否纬，則存在若干整數(shù)對x，y蛋褥，使得

貝祖定理

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

其中當(dāng)gcd(a,b)=1時临燃，則證明a和b都是素數(shù)，即

a和b都是素數(shù)

十一烙心、歐幾里得擴展算法

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

算法證明：

令

設(shè)置參數(shù)變量

則c可以表示為商q和余數(shù)r的線性形式

c表示為商q和余數(shù)r

我們已知線性方程組為

已知線性方程組

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

化簡1

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

化簡2

下面我們將參數(shù)表做如下變化

參數(shù)表變化

經(jīng)過上述變化匙瘪，將參數(shù)變化帶入化簡2铆铆，得到

變化1

將參數(shù)變化帶入線性方程組的第二個方程蝶缀，得到

變化2

綜上所述，可以看到線性方程組經(jīng)過參數(shù)表變化后保持了原線性方程組的正確性

至此薄货，我們總結(jié)出歐幾里得擴展算法的步驟為：

（1）初始化參數(shù)：x' = y = 1翁都，x = y' = 0，c = a谅猾，d = b

（2）令q和r表示d除以c得到的商和余數(shù)

（3）如果余數(shù)r不為0柄慰，則進(jìn)入循環(huán)，按照變化參數(shù)列表更新參數(shù)税娜，返回第(2)步

（4）如果余數(shù)r為0坐搔，則算法終止，返回x和y即為所求

我們用python實現(xiàn)歐幾里得擴展算法敬矩，并測試求解：47x + 30y = 1的解概行？

歐幾里得擴展算法

計算結(jié)果

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

十二、大整數(shù)快速冪算法

如果我們要計算a的11次方缩筛，則按照冪運算的定義消略，需要執(zhí)行11次乘法

如果將指數(shù)11寫成二進(jìn)制，則

快速冪原理

可以看到經(jīng)過上述變化瞎抛，計算a的11次方只需要執(zhí)行3次乘法即可艺演，這就是快速冪算法的原理

快速冪算法步驟為：

（1）將冪指數(shù)視為二進(jìn)制進(jìn)入循環(huán)

（2）判斷指數(shù)二進(jìn)制權(quán)位是否為奇數(shù)，如果為奇數(shù)桐臊，則累乘結(jié)果

（3）每次循環(huán)對指數(shù)進(jìn)行左移位運算胎撤，以及對底數(shù)進(jìn)行累乘運算

我們用python實現(xiàn)歐幾里得擴展算法，并測試求解：12345678^56789

快速冪算法

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

比較結(jié)果

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

十三伤提、大整數(shù)快速冪取模算法

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

快速冪取模算法的核心

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

我們用python實現(xiàn)歐幾里得擴展算法认烁，并測試求解：123456789^987654 %?65537

快速冪取模算法

比較結(jié)果

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

至此却嗡，有了上述數(shù)論的基礎(chǔ)知識和相應(yīng)的算法舶沛，將這些數(shù)學(xué)理論和算法串聯(lián)，我們就可以開始RSA算法的實戰(zhàn)

案例代碼見：RSA加密解密算法—數(shù)論基礎(chǔ)