本章涉及知識(shí)點(diǎn)
1、素?cái)?shù)的定義
2、尋找素?cái)?shù)算法—短除法
3、尋找素?cái)?shù)算法—篩選法
4、互質(zhì)關(guān)系
5、歐拉函數(shù)的證明
6、歐拉定理
7、費(fèi)馬小定理
8、模反元素
9、歐幾里得算法—求最大公約數(shù)
10、貝祖定理
11、歐幾里得擴(kuò)展算法—求二元一次方程的解
12、大整數(shù)快速冪算法
13、大整數(shù)快速冪取模算法
14、總結(jié)
一、素?cái)?shù)的定義
質(zhì)數(shù)又稱素?cái)?shù)，指在一個(gè)大于1的自然數(shù)中，除了1和本身之外，無(wú)法被其他自然數(shù)整除的數(shù)
素?cái)?shù)具有下列獨(dú)特的性質(zhì)：
（1）素?cái)?shù)p的因子有且只有兩個(gè)：1和p
（2）素?cái)?shù)一定是奇數(shù)
（3）任意一個(gè)大于1的正整數(shù)N，一定可以質(zhì)因式分解為它的有限個(gè)質(zhì)因子之積
（4）素?cái)?shù)的個(gè)數(shù)是無(wú)限的
（5）所有大于10的素?cái)?shù)中，其個(gè)位數(shù)只能是1,3,7,9其中之一
（6）一個(gè)充分大的偶數(shù)一定可以寫成：一個(gè)素?cái)?shù)加上一個(gè)最多由2個(gè)質(zhì)因子所組成的合成數(shù)
如果將素?cái)?shù)p表示成極坐標(biāo)方程
我們將第500到第5000的素?cái)?shù)畫在笛卡爾坐標(biāo)系來(lái)觀察其分布：
可以看到素?cái)?shù)的分布呈螺旋形狀，這種現(xiàn)象又叫質(zhì)數(shù)螺旋
幾百年之間，無(wú)數(shù)世界頂級(jí)的數(shù)學(xué)家，研究一生始終無(wú)法精確的證明素?cái)?shù)的表達(dá)式以及其分布的規(guī)律
二、尋找素?cái)?shù)算法—短除法
問(wèn)題定義：在給定范圍n之內(nèi)，找到所有素?cái)?shù)
（1）方法一：
最直接的方法就是從定義出發(fā)，對(duì)于任意整數(shù)p，用[2，p-1]去整除p，如果發(fā)現(xiàn)p可以被整除，p就不是素?cái)?shù)
顯然，這個(gè)方法的效率簡(jiǎn)直低的讓人難以接受，優(yōu)化空間非常大
（2）方法二：
顯然偶數(shù)不是素?cái)?shù)，對(duì)于任意奇數(shù)p，用[3，5，...，p-2]去整除p，如果發(fā)現(xiàn)p可以被整除，p就不是素?cái)?shù)
這個(gè)方法的效率稍微高了一些，但是其本質(zhì)和方法一沒(méi)有任何區(qū)別，只是整除系數(shù)范圍縮小到奇數(shù)
（3）方法三：
利用質(zhì)因式分解的思想，對(duì)于任意奇數(shù)p，用小于p的素?cái)?shù)去整除p，如果發(fā)現(xiàn)p可以被整除，p就不是素?cái)?shù)
這個(gè)方法的計(jì)算效率又提高了一些，將奇數(shù)級(jí)別的除數(shù)縮小到質(zhì)數(shù)范圍
（4）方法四：
利用平方根條件，對(duì)于任意奇數(shù)p，用小于p的平方根的素?cái)?shù)去整除p，如果發(fā)現(xiàn)p可以被整除，p就不是素?cái)?shù)
這個(gè)方法將素?cái)?shù)級(jí)別的除數(shù)又縮小到不大于其平方根的范圍，我們稱之為短除法
我們用python實(shí)現(xiàn)短除算法，并測(cè)試尋找在[2，2^22]范圍內(nèi)所有的素?cái)?shù)的算法效率
從短除算法尋找結(jié)果中，可以看到該算法花費(fèi)了13秒，找到295947個(gè)素?cái)?shù)
三、尋找素?cái)?shù)算法—篩選法
除了上述的短除算法，是否存在更加高效的算法來(lái)尋找素?cái)?shù)？
的確存在一個(gè)非常高效的算法—篩選法，其設(shè)計(jì)思想是：
（1）將n個(gè)數(shù)字全部放進(jìn)數(shù)組，并都置為肯定狀態(tài)
（2）將數(shù)組下標(biāo)是偶數(shù)的數(shù)字全部置為否定狀態(tài)
（3）依次遍歷數(shù)組長(zhǎng)度的平方根個(gè)數(shù)字
（4）如果當(dāng)前數(shù)字處于被肯定的狀態(tài)，則將其倍數(shù)的數(shù)字狀態(tài)置為否定
我們用python實(shí)現(xiàn)篩選算法，并測(cè)試尋找在[2，2^22]范圍內(nèi)所有的素?cái)?shù)的算法效率
從篩選算法尋找結(jié)果中，可以看到該算法只花費(fèi)了1.16秒，就找到295947個(gè)素?cái)?shù)
至此我們可以總結(jié)出比較上述找尋素?cái)?shù)的兩種算法
（1）短除算法：使用了嚴(yán)進(jìn)寬出的思想，對(duì)每個(gè)數(shù)字的判斷非常嚴(yán)格，保證每次找到的數(shù)字都是素?cái)?shù)，時(shí)間復(fù)雜度較高
（2）篩選算法：使用了寬進(jìn)嚴(yán)出的思想，一步步篩選（否定），最后保留下來(lái)的數(shù)字才是素?cái)?shù)，利用空間換取時(shí)間來(lái)大大降低了時(shí)間復(fù)雜度
四、互質(zhì)關(guān)系
公因數(shù)只有1的兩個(gè)數(shù)字，稱為互質(zhì)關(guān)系
互質(zhì)具有下列獨(dú)特的性質(zhì)：
（1）任意兩個(gè)素?cái)?shù)一定是互質(zhì)關(guān)系
（2）如果一個(gè)數(shù)是素?cái)?shù)，另一個(gè)數(shù)字不是它的倍數(shù)，則二者互質(zhì)
（3）較大的數(shù)是素?cái)?shù)，則二者互質(zhì)
（4）相鄰的兩個(gè)自然數(shù)一定互質(zhì)
（5）相鄰的兩個(gè)奇數(shù)一定互質(zhì)
（6）1和任意數(shù)互質(zhì)
五、歐拉函數(shù)的證明
問(wèn)題的提出：
給定任意正整數(shù)n，問(wèn)在小于等于n的正整數(shù)之中，有多少個(gè)數(shù)字與n構(gòu)成互質(zhì)關(guān)系？
我們定義歐拉函數(shù)φ(n)來(lái)表示這個(gè)值，則分析討論φ(n)可能存在的情況
（1）當(dāng)n等于1的情況：
則根據(jù)互質(zhì)的性質(zhì)6可以得到
（2）當(dāng)n等于素?cái)?shù)p的情況：
則n以下的數(shù)字和n都互質(zhì)
（3）當(dāng)n等于素?cái)?shù)的某一個(gè)次方，即n = p^k的情況：
則小于等于p^k且與p^k不互質(zhì)的個(gè)數(shù)有
則φ(n) = （p^k個(gè)數(shù)字） -? （小于等于p^k且與p^k不互質(zhì)的個(gè)數(shù)），即
（4）當(dāng)n等于兩個(gè)素?cái)?shù)的乘積，即n=p*q（p和q互質(zhì)）的情況：
則φ(n) =φ(pq)滿足乘法分配律，即?
（5）當(dāng)n等于任意大于1的正整數(shù)的情況：
由素?cái)?shù)的性質(zhì)3（質(zhì)因數(shù)分解）可以得到
其中p1、p2...pr都是n的質(zhì)因數(shù)
則根據(jù)上述(3)和(4)的分析結(jié)果，可以推導(dǎo)出
綜上分析，我們得到歐拉函數(shù)的通用計(jì)算方式為
六、歐拉定理
歐拉定理是解決同余的性質(zhì)，其定義為：
如果p和q為正整數(shù)，且pq互質(zhì)，則
顯然，我們可以用歐拉函數(shù)來(lái)判斷兩個(gè)正整數(shù)是否互質(zhì)
七、費(fèi)馬小定理
費(fèi)馬小定理是歐拉定理的特殊情況，其定義為：
如果p和q為正整數(shù)，且pq互質(zhì)，且q是素?cái)?shù)，則q的歐拉函數(shù)為
則歐拉定理可以寫為
八、模反元素的定義
模反元素指：如果兩個(gè)正整數(shù)p和q互質(zhì)，那么一定存在一個(gè)或多個(gè)整數(shù)b，使得
我們可以通過(guò)歐拉函數(shù)的定義來(lái)證明模反元素的必然存在
可以看到p的φ(n) -1次方就是p的一個(gè)模反元素
九、歐幾里得算法—求最大公約數(shù)
問(wèn)題提出：計(jì)算兩個(gè)正整數(shù)a和b的最大公約數(shù)？
歐幾里得算法，又稱輾轉(zhuǎn)相除法，其定義最大公約數(shù)滿足：
下面我們來(lái)證明該算法
設(shè)a>b>1，則
其中k為a除以b的商，r為a對(duì)b取模，即
設(shè)d是a和b的一個(gè)公因數(shù)，則d可以整除a和b，即
又因?yàn)閞 = a - kb，則
可以看到d也可以整除r，即
綜上，我們可以證明出
十、貝祖定理
貝祖定理是初等數(shù)論里提出的一個(gè)定理，它的定義為：
如果有兩個(gè)正整數(shù)a和b，則存在若干整數(shù)對(duì)x，y，使得
該定理說(shuō)明：a和b的最大公約數(shù)滿足a和b的線性組合
其中當(dāng)gcd(a,b)=1時(shí)，則證明a和b都是素?cái)?shù)，即
十一、歐幾里得擴(kuò)展算法
歐幾里得擴(kuò)展算法是用來(lái)求解出貝祖等式ax+by=gcd(a，b)的一個(gè)解(x，y)，即求解二元一次線性方程
算法證明：
令
則c可以表示為商q和余數(shù)r的線性形式
我們已知線性方程組為
將c帶入第一個(gè)方程，得到
將d的表達(dá)式帶入上式，得到
下面我們將參數(shù)表做如下變化
經(jīng)過(guò)上述變化，將參數(shù)變化帶入化簡(jiǎn)2，得到
將參數(shù)變化帶入線性方程組的第二個(gè)方程，得到
綜上所述，可以看到線性方程組經(jīng)過(guò)參數(shù)表變化后保持了原線性方程組的正確性
至此，我們總結(jié)出歐幾里得擴(kuò)展算法的步驟為：
（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實(shí)現(xiàn)歐幾里得擴(kuò)展算法，并測(cè)試求解：47x + 30y = 1的解？
可以看到x=-7，y=11，帶入到方程計(jì)算得-7*47+30*11=1，確實(shí)是該二元方程的一組整數(shù)解
十二、大整數(shù)快速冪算法
如果我們要計(jì)算a的11次方，則按照冪運(yùn)算的定義，需要執(zhí)行11次乘法
如果將指數(shù)11寫成二進(jìn)制，則
可以看到經(jīng)過(guò)上述變化，計(jì)算a的11次方只需要執(zhí)行3次乘法即可，這就是快速冪算法的原理
快速冪算法步驟為：
（1）將冪指數(shù)視為二進(jìn)制進(jìn)入循環(huán)
（2）判斷指數(shù)二進(jìn)制權(quán)位是否為奇數(shù)，如果為奇數(shù)，則累乘結(jié)果
（3）每次循環(huán)對(duì)指數(shù)進(jìn)行左移位運(yùn)算，以及對(duì)底數(shù)進(jìn)行累乘運(yùn)算
我們用python實(shí)現(xiàn)歐幾里得擴(kuò)展算法，并測(cè)試求解：12345678^56789
比較快速冪算法和直接連乘法的效率
可以看到，快速冪算法的效率非常高
十三、大整數(shù)快速冪取模算法
快速冪取模算法基于下面這個(gè)取模等價(jià)式子
它的思路和快速冪算法一致，在循環(huán)過(guò)程加入取模運(yùn)算即可
我們用python實(shí)現(xiàn)歐幾里得擴(kuò)展算法，并測(cè)試求解：123456789^987654 %?65537
可以看到，加入取模計(jì)算后，快速冪取模算法幾乎是瞬間完成計(jì)算
至此，有了上述數(shù)論的基礎(chǔ)知識(shí)和相應(yīng)的算法，將這些數(shù)學(xué)理論和算法串聯(lián)，我們就可以開(kāi)始RSA算法的實(shí)戰(zhàn)
案例代碼見(jiàn)：RSA加密解密算法—數(shù)論基礎(chǔ)
