【正文】 2/13/2022 83 密碼學(xué)的數(shù)論基礎(chǔ) ?素?cái)?shù) ?Fermat定理和 Euler定理 ?素性測(cè)試 ?中國(guó)剩余定理 ?離散對(duì)數(shù) Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 84 素?cái)?shù) ?一個(gè)只能被 1以及自身整除并且大于 1的整數(shù)稱(chēng)為素?cái)?shù)，也稱(chēng)為質(zhì)數(shù) ?小于 200的素?cái)?shù)： 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 ?合數(shù)： 4， 6， 8， 9， 10， 12， … Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 85 關(guān)于素?cái)?shù)的一些疑問(wèn) ?素?cái)?shù)有多少個(gè)？ ?如何尋找素?cái)?shù)？ ?如何判斷一個(gè)數(shù)是否為素?cái)?shù)？ ?例如 2022 ?例如 9 909 408 073？ Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 86 ?歐幾 里得（ Euclid of Alexandria，約 公元前 330 ? 約 公元前 275） ?歐幾 里得的 《 幾何何原本 》 是用公理方法建立 演繹數(shù)學(xué)體系 的最早典 范 ?歐幾里德在他的 幾何原本 中證明了素?cái)?shù)有無(wú)窮多 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 87 素?cái)?shù)有多少？ ?定理：素?cái)?shù)有無(wú)窮多個(gè) ?證明：假設(shè)素?cái)?shù)只有有限多個(gè)，并記最大的素?cái)?shù)為 P，定義 Q = 2 ? 3 ? 5 ? 7 ? … ? P + 1，根據(jù)假設(shè)， Q是一個(gè)合數(shù)，同時(shí)用 Q除以任何素?cái)?shù)都余 1，所以所有的 素?cái)?shù)都不是 Q的因數(shù)，這是不可能的，所以素?cái)?shù)有無(wú)窮多個(gè)。 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 88 篩法求素?cái)?shù) ?尋找在給定范圍內(nèi)的素?cái)?shù)排列，有 埃拉托斯特尼（ Eratosthenes）篩法 ?Eratosthenes，公元前 276年～公元前 194年，希臘數(shù)學(xué)家、地理學(xué)家、天文學(xué)家，主要貢獻(xiàn)是設(shè)計(jì)出經(jīng)緯度系統(tǒng)，計(jì)算出地球的直徑 ?埃拉托斯特尼篩法是一種簡(jiǎn)單的列出小于給定數(shù)的所有素?cái)?shù)的算法 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 89 篩法求素?cái)?shù) ?找指定范圍內(nèi)所有素?cái)?shù) ?首先把 2 ～ m 內(nèi)所有數(shù)放入篩中 ,然后找出篩中最小的素?cái)?shù) ,并將該數(shù)在范圍之內(nèi)的所有倍數(shù)的數(shù)去掉 ,依次進(jìn)行 ,直到篩中的最小的素?cái)?shù)已經(jīng)超出 m 的范圍 ?最小素?cái)?shù)去掉所有倍數(shù)以后的數(shù)中近鄰的數(shù)即是下次循環(huán)的最小素?cái)?shù) ?退出的條件是 :最小素?cái)?shù)已經(jīng)等于最大的數(shù) ,即指定的查找范圍 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 90 篩法求素?cái)?shù) ?列出如下這樣以 2開(kāi)頭的序列 ?2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ?標(biāo)出序列中的第一個(gè)素?cái)?shù)，主序列變成 ?2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ?將剩下序列中 2的倍數(shù)劃掉（用紅色標(biāo)出），主序列變成 ?2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ?如果現(xiàn)在這個(gè)序列中最大數(shù)小于第一個(gè)素?cái)?shù)的平方，那么剩下的序列中所有的數(shù)都是素?cái)?shù)，否則返回第二步。 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 91 篩法求素?cái)?shù) ?本例中，因?yàn)?25大于 2的平方，我們返回第二步 ?剩下的序列中第一個(gè)素?cái)?shù)是 3，將主序列中 3的倍數(shù)劃出（紅色），主序列變成： ?2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ?25仍然大于 3的平方，所以我們還要返回第二步 ?現(xiàn)在序列中第一個(gè)素?cái)?shù)是 5，同樣將序列中 5的倍數(shù)劃出，主序列成了： ?2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ?因?yàn)?25等于 5的平方，跳出循環(huán) . ?去掉紅色的數(shù)字， 2到 25之間的素?cái)?shù)是： 2 3 5 7 11 13 17 19 23 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 92 尋找素?cái)?shù) ?數(shù)學(xué)家一直努力找尋產(chǎn)生素?cái)?shù)的公式，但截至目前為止，并沒(méi)有一個(gè)函數(shù)或是多項(xiàng)式可以正確產(chǎn)生所有的素?cái)?shù)。歷史上有許多試驗(yàn)的例子，如默森，費(fèi)馬等 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 93 尋找素?cái)?shù) ?默森（ Mersenne，1588 ? 1648） ?法國(guó)人，神父 ?默森數(shù) （ 1644） ： 2p ? 1 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 94 默森數(shù) 23 ? 1 = 7 25 ? 1 = 31 27 ? 1 = 127 211 ? 1 = 2047 = 23 ? 89 213 ? 1 =8191 217 ? 1 = 131071 219 ? 1 = 524287 223 ? 1 = 838607 = 47 ? 178481 229 ? 1 = 536870911 = 233 ? 2304167 231 ? 1 = 2147483647 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 95 默森數(shù) ?于是默森提出如下的猜想： ?當(dāng) p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257時(shí)， 2p ? 1會(huì)是素?cái)?shù) ?對(duì)于其余小于 257的 44個(gè)素?cái)?shù) p， 2p ? 1 都是合數(shù) ?但后來(lái)的數(shù)學(xué)家發(fā)現(xiàn)，當(dāng) p = 67和 257時(shí)， 2p ? 1 不是素?cái)?shù)；但當(dāng) p = 61, 89, 107 時(shí)， 2p ? 1卻是素?cái)?shù) ！ ?實(shí)際上，如果對(duì)某正整數(shù) n， 2n1 是素?cái)?shù)，則 n 一定是素?cái)?shù) Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 96 當(dāng)今發(fā)現(xiàn)的最大素?cái)?shù) 第 42個(gè)一致的默森數(shù) 2259649511 2022年 2月 26日公布 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 97 費(fèi)馬 ?費(fèi)馬 （ Pierre de Fermat。 1601 ? 1665） ?法國(guó)人 ?律師， 1631 年出任圖盧茲議院顧問(wèn) ?業(yè)余研究數(shù)學(xué) ?他是幾何學(xué)、概率論、微積分、數(shù)論等領(lǐng)域的先驅(qū) Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 98 費(fèi)馬數(shù) 220 + 1 = 3 221 + 1 = 5 222 + 1 = 17 223 + 1 = 257 224 + 1 = 65537 于是費(fèi)馬猜想所有寫(xiě)成 22n + 1 形式的數(shù)都是素?cái)?shù) Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 99 歐拉 ?歐拉 （ Leonhard Euler。 1707 1783） ?瑞士數(shù)學(xué)家 ?13歲入大學(xué)， 17歲取得碩士學(xué)位 ?證明 不是 素?cái)?shù) 12 52 ?Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 100 證明 F5不是素?cái)?shù) 記 a = 27 和 b = 5，則 a ? b3 = 3 ∵ 1 + ab ? b4 = 1 + (a ? b3)b = 1 + 3b = 16 = 24 ? 225 + 1 = 232 + 1 = (2a)4 + 1 = 24a4 + 1 = (1 + ab ? b4)a4 + 1 = (1 + ab)a4 + (1 ? a4b4) = (1 + ab)[a4 + (1 ? ab)(1 + a2b2)] 即 232 + 1 可被 1 + ab = 641 整除！ 注 ： 232 + 1 = 4 294 967 297 = 641 ? 6 700 417 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 101 高斯 ?高斯 （ Carl Friedrich Gauss， 1777 ? 1855） ?德國(guó)數(shù)學(xué)家，近代數(shù)學(xué)的奠基人之一，人稱(chēng) 「 數(shù)學(xué)王子 」 ?19歲 提出以直尺和 圓規(guī)繪畫(huà) 正 17邊 形的方法。 ?提出繪畫(huà)素?cái)?shù)多邊形形的充分必要條件是該 素?cái)?shù)必定是費(fèi)馬數(shù)！ Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 102 素?cái)?shù)分布 ?素?cái)?shù)定理 描述素?cái)?shù)的大致分布情況 其中 ?(n)表示不大于 n 的素?cái)?shù)的數(shù)目，例如 ?(10) = 4，?(100) = 25 …… 等 ?若 n 趨向無(wú)窮 大， 則 ?(n) / n 趨 向 0 （ 即 當(dāng) n 越大 時(shí)，素?cái)?shù)的 「密度」 會(huì) 越 小 ） 1)(limln????nnnnSun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 103 算術(shù)基本定理 ? 任一正整數(shù)都能表成若干素?cái)?shù)的乘積： 為素?cái)?shù)，并且若不計(jì)的排列次序，上述表法唯一 ?素因子標(biāo)準(zhǔn)分解式：任何正整數(shù)都可以唯一地表示成 12 sn p p p?( 1 , 2 , , )ip i s?0 , , 2121 21 ????? iss ppppppa s ???? ??Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 104 費(fèi)馬小定理 ?Fermat定理 其中 為素?cái)?shù)， ?素性判定： Fermat 定理的逆定理不成立，滿(mǎn)足條件的合數(shù)叫 Carmichael 數(shù)，最小的是 561=3 11 17。 pa p m o d 11 ??1),g c d ( ?papSun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 105 歐拉函數(shù) ?指小于 n并且與 n互素的正整數(shù)的個(gè)數(shù)，記 ?(n) ?對(duì)于素?cái)?shù) p有： ?(p) = p1 ?對(duì)于 n =pq， p， q均為素?cái)?shù)，有 ?(pq) = (p1)(q1) ?pq = of numbers from 1 to pq ?p = of multiples of q up to pq ?q = of multiples of p up to pq ?1 = of multiple of both p and q up to pq ??(pq) = pq – p – q + 1 = (p1)(q1) ?例如 ??(37) = 36 ??(21) = (3–1) (7–1) = 2 6 = 12 Sun Yatsen University 169。 廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 | 2/13/2022 106 歐拉函數(shù) ?積性函