數學實驗之五---素數課件

1、數學實驗之五 - 素數中國科學技術大學數學系陳發(fā)來實驗內容素數的個數素數表的構造素數的判別最大的素數求解素數的公式素數的分布1、素數的個數算術基本定理：任何整數都可以分解為設 為所有的素數?？疾?如果N為合數，則N必以某些 為因子。這是不可能的！ 雖然素數有無窮多個，但隨著整數范圍越來越大，素數似乎越來越稀少。 1，100-25 1000,1100-16 100000, 100100-6 10000000,10000100-22、素數表的構造Eratosthenes篩法 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2

2、5 26 27 28 29 30 31 32 33 經過眾多學者的艱辛努力, D.N.Lehmer 于 1914年編織出了10000000以內的素數表。試除法 假設我們已經找到了前n個素數p_1=2, p_2=3, .,p_n, 為了尋找下一個素數我們從p_n+2開始依次檢驗每一個整數N, 看N是否能被某個p_i, i=1,2,.,n整除. 如果N能被前面的某個素數整除, 則N為合數. 否則N即為下 一個素數p_n+1. 為提高算法的效率，只需用不超過 的素數去除N。3、素數的判別威爾遜判別法 n是素數的充要條件是 這里 是指 a-b 被p整除。 不過該算法的運算量為O(nlogn2),計算量

3、太大。Fermat判別法 如果p是素數，a與p互素，那么實際上，大約2500年前，中國古代數學家就發(fā)現了上述結論。他們由此得出：如果 ,則n為素數。該判別法的運算量為O(log3n). 通過編程計算發(fā)現，反過來結論并不成立。例如，但是341=11x34為合數！稱使得成立的p為偽素數。注意同余的計算：進一步，偽素數有多少個？ 答案是無窮多個。實際上，數學家邁羅在1903年證明，如果n為偽素數，那么2n-1也是偽素數。 不過，同素數個數相比，偽素數的個數非常少。例如，在2x1010之內，偽素數不到素數的百萬分之三。因此，可以認為 Fermat定理的逆定理幾乎成立。利用偽素數表，可以給出判別素數的新

4、方法：如果p不整除2n-1, 則p為合數；如果p整除2n-1, 且在偽素數表中，則p為合數，否則，p是素數。偽素數可以推廣到a-偽素數。令人驚奇的是，存在這樣的數p, 它對任何a都是偽素數。例如，561=3x11x17就是這樣一個偽素數，即這樣的數稱為絕對偽素數，也稱邁克爾數。如果邁克爾數只有有限個，則對nM, 素數的判別變得比較容易。但邁克爾可能有無限個，這使得直接用Fermat 定理判別素性變得困難。n-1檢驗法 假設n-1=FR, FR, gcd(F,R)=1. 如果對F的每一個素因子q都存在一個整數a1滿足 則n是素數?；趶V義黎曼猜想的判別 1976年，繆內發(fā)現了素性判別與黎曼猜想之

5、間的一個深刻聯系。他的結論是： 在廣義黎曼假設下，存在常數C, 對任何整數n, 若n為合數，則存在aC(logn)2 使得維路于1978年指出，上述常數C=70.由此可以設計如下多項式算法： 對任意n, 依次對a=1,2,70(logn)2檢驗上式是否成立。若對每一個a都不成立，則n為素數。否則，n 為合數。 上述算法的運算量為O(logn)5.年數學家Adleman, Rumely, Cohen和Lenstra研究出一種非常復雜、具有高度技巧的素數判別方法，檢驗一個位數的素性只需秒，對一個位數，只要秒，而一個位數只用秒。如果用試除法，判別一個位數的素性要一百億年！概率判別法Lehmann:

6、給定p, 判斷它是否為素數：（）選擇一個小于p的隨機數a;（）如果a與p不互素，則p為合數；（）計算 J=a(p-1) mod p；（）如果 J1或-1, 那么p為合數；（）如果 J=1或-1,那么p不是素數的可能性最多是50%.重復k次實驗，那么p不是素數的可能性不超過1/2k.利用上述算法可以產生大的隨機素數：（1）產生隨機數p;（2）確保p不被較小的素數整除。（3）產生隨機數a, 利用上述算法檢測p的素性。直到經過多次測試為止。素性判別的多項式算法給定一個n位的整數，假設某一算法能在f(n)步內判斷出該整數是否素數。如果f(n)是一個多項式的話，則稱該算法具有多項式復雜性，稱該問題是“多

7、項式可解的”。如果不存在一個算法其具有多項式的計算復雜性，則稱該問題屬于NP問題。2002年8月，印度理工大學計算機系的三位學者提出了整數素性判別的多項式算法！即素性判別問題是P類問題。他們指出算法復雜性一般為O(n12)。如果提供某些啟發(fā)線索的話，算法的復雜性可以降到O(n6)甚至O(n3).一個令人關注的問題是，該算法是否會威脅現有的RSA公鑰密碼體系的安全？4、最大的素數Mersenne數 形如 的數稱為Mersenne數。利用Mersenne數可以構造出非常大的素數。 很顯然，如果n是合數，則M_n也為合數，但n為素數時，M_n不一定為素數。例如，M_11=2047=23x89是合數。

8、 1644年Mersenne宣稱，對n=2,3,5,13, 17,19,31,67,127,257, M_n都是素數，而且對其它n257, M_n都是合數。 然而，后人證明M_67, M_257不是素數，而M_61, M_89, M_107都是素數。截止2002年2月, 數學家僅發(fā)現了39個 Mersenne素數. n 位數 時間86143259621982110503332651983132049397511983216091650501985 n 位數 時間756839 227832199285943325871619941257787378632199613982694209211996

9、29762218959321997302137790952619986972593209896019991346691740539452002Mersenne數素性的判別方法 定義數列u_0=4, u_k+1= u_k2-2 (mod M_n), k=1,2,., n. 如果u_n-1 =0(mod M_n), 則M_n為素數. 否則, M_n 為合數. 關于Mersenne素數的進一步問題： （1）Mersenne素數是否有無窮多個？ （2）對什么樣的n,M_n是素數？是否存在求n的公式？至少使M_n為素數的n應該具有什么性質？ （3）如果M_n是合數，如果分解M_n？5、生成素數的公式是否

10、存在單變量整系數的多項式, 它只生成素數并且生成所有的素數? 更一般地,是否存在一個生成素數的多變量函數公式? 如果這樣的公式不存在, 能否找到一個雖不能給出全部但能給出無窮多個素數(且只給出素數)的公式?Fermat數 形如F_n=22n+1的數被稱為 Fermat數。 Fermat宣稱，對所有的整數n, F_n永遠是素數。 的確, F_0=3, F_1=5, F_2=17, F_3=257, F_4=65537都是素數。 但Euler指出F_5=4294967297=6416700417 是合數。后人驗證出F_n (n4)都是合數。Fermat數F_n與正多邊形做圖有緊密的聯系. 古代數學

11、家認為，當n為大于6的素數時，正n邊形不能用圓規(guī)與直尺做出。但是，在1796年，19歲的德國數學家Gauss找到了用直尺與圓規(guī)做正17邊形的方法。這一輝煌的成果轟動了整個數學界。五年后他進一步證明了: 一個正n邊行可用直尺與園規(guī)作圖的充要條件是, n=2k或者n=2k p_1 p_2. p_r, 其中p_1,p_2,.,p_r為不同的Fermat數. 特別地, 正17邊形可以用直尺與園規(guī)做出. 此后，數學家梨西羅與蓋爾美斯給出了正257邊形與正65537邊形的做圖法！關于Fermat數主要研究的問題是：（1）如何分解Fermat數？（2）Fermat素數是否只有有限個？（3）Fermat合數是

12、否有無窮多個？（4）Fermat數有沒有平方因子？Euler素數生成公式 Euler曾研究過公式：f(n)=n2+n+41. 可以驗證，當n=0,1,39時，f(n)都是 素數，但f(40)是合數。有趣的是，公式能給出相當多的素數。公式n2+n+41有一個非常奇特的性質. 為揭示這一特性, 我們考察它的二次求根公式的判別式d=12-4141 =-163. 163有什么特別的地方？有! 請看 作為Hilbert第十問題的一個推論, 馬蒂雅舍維奇證明了: 存在一個多元多項式P(x_1,x_2,.,x_n), 其正值構成的集合恰好是素數的全體. 遺憾的是, 他并沒有給出怎樣具體地構造這樣的多項式.

13、后經眾多數學家的努力, 終于在1977年構造出了一個具有26個變量25次的素數生成多項式! 6、素數的分布素數沿數軸的分布 （1）隨著整數范圍的擴大，素數是不是越來越稀疏？稀疏的程度是否單調地增加？（2）相鄰素數之間的間隔值有哪些? 它們各重復多少次? 哪些間隔值的重復次數多? 最大間隔值是多少? 隨整數范圍擴大, 最大間隔值是否也隨之增大?（3）間隔差為2的素數對是否有無窮多個? 更一般地, 間隔差為某一個固定偶數的素數對是否有無窮多個? 是否存在相鄰的素數, 其間隔值可以任意大?用(n)表示不超過n的素數的個數, (m,n)表示區(qū)間m,n內素數的個數. 固定d,繪制點列（i, (3i,3i

14、+d), i=1,2,N.將素數從小到大順序排列p_1=2, p_2=3, ., 用d_n=p_n+1-p_n表示相鄰素數間的間隔. 計算d_1,d_2,., d_N(如N=1000, 10000), 然后將點(p_n,d_n)標在平面坐標系中. 素數的個數 在二維坐標平面上標出點列(n, (n), n=1,2,., N(取不同的N, 如1000, 10000等). 也可以用折線將點列連接起來. 觀察(n)趨于無窮的趨勢.由此猜測關于素數個數的近似公式首先是Gauss 于1792年給出的,但他當時沒能給出證明. 勒讓德也曾給出后來，Gauss還給出了近似公式：最接近的公式是由Rieman 猜想

15、導出的：這里1852年，俄國數學家切比雪夫證明了這里a=0.92, b=1.055. 1892年，英國數學家希爾維斯特改進切比雪夫的結果，得到a=0.956, b=1.044.1896,Hadamard與Poussin利用復變函數的理論加以證明. 素數定理的初等證明于1949年著名數學家Erdos獲得。Riemann猜想與素數的分布有緊密的聯系。不過Riemann猜想至今仍未被證明, 它無疑是數學上最著名的難題之一。7、 進一步的思考問題Goldbach 猜想 Goldbach于1742年給大數學家Euler的信中提出了兩個猜想, 即每個不小于6的偶數都可以表為兩個奇素數之和; 每個不小于9的

16、奇數可以表為三個奇素數之和. Euler在隨后的復信中寫道: 任何不小于6的偶數都是兩個奇素數之和, 雖然我不能證明它, 但我確信無疑這是完全正確的定理. 這就是著名的Goldbach猜想的由來. 兩百多年來, 無數數學家花費了大量的心血都未能解決這一問題.目前，有人驗證到1014,命題仍然正確。1900年，Hilbert在巴黎世界數學家大會上提出23個問題供20世紀數學家研究。其中第8問題中將Goldbach猜想作為最重要的問題之一提出。1912年，在第五屆世界數學家大會上，數學家蘭道指出，即使證明下面較弱的命題，也是現代數學所力不能及的。任何整數都可以表示為不超過C個素數之和。1921年英

17、國數學家Hardy在哥本哈根召開的數學會議上說，Goldbach猜想的困難程度可以跟任何沒解決的數學問題想比1930年，蘇聯數學家什尼爾列曼證明，任意整數都可以表為不超過k個素數之和,且k800000.1935年， k=2208 （蘇聯，羅曼諾夫）1936年，k=71 (德國，海爾布倫）1937年，k=67（意大利，里奇）1950年，k=20（美國，夏彼得）1956年，k=18（中國，尹文霖）1976年，k=6 (旺格漢）1937，蘇聯人維諾格拉夫證明，充分大的奇數可以表為三個素數的和。另一條路線：將大偶數表示為s個素數之積加上t個素數之和。記為“s+t”.年份證明者國家結果1920布龍挪威9

18、+91924拉特馬赫德國7+71938布赫夕太勃蘇聯5+5; 4+41948蘭恩尼匈牙利1+C1956王元中國3+4；3+31962潘乘洞中國1+51962王元中國1+41965布赫夕太勃蘇聯1+31966陳景潤中國1+2Fermat大定理 設n是大于2的整數，則方程 無不存在非平凡的整數解。 Fermat 本人證明了n=4的情形。1753年，Euler證明了n=3.1825年，Dirchlet與Legendre證明了n=5.1832年，法國女數學家索非熱爾曼證明：如果n和2n+1為素數，Fermat大定理成立。1839年，拉梅證明了n=7.1847年，德國數學家Kummer證明了對n2, 方

19、程只有有限個解。1993年，Princeton大學的教授威爾斯宣布證明了Fermat定理。但數學家發(fā)現了證明中的一個漏洞。經過九個月的努力威爾斯修正了這一錯誤，這標志著Fermat大定理被徹底征服。威爾斯的證明完全采用了全新的路線，用到了現代數學的許多分支：橢圓曲線論，模形式論，伽羅華表示論等。所謂橢圓曲線是如下形式的曲線：橢圓曲線與模形式之間有緊密的聯系。50年代，日本數學家谷山豐和志村五郎猜測：有理數域上的每條橢圓曲線都存在模形式。被乘為“谷山-志村”猜想。60年代，有人將Femat 方程與橢圓曲線聯系起來。1984年，佛賴證明，如果Fermat大定理不成，則由Fermat方程確定的橢圓曲

20、線不可能是模形式，這與谷山-志村猜想矛盾！因此，要證明Fermat大定理，只需證明谷山-志村猜想。威爾斯所做的正是證明了該猜想。大整數的素因子分解 正如判斷一個大數的素性一樣, 將一個大整數分解為素因子的乘積是一件相當艱難的事情, 迄今尚無一種通用有效的方法(試除法顯然是不用考慮的). 目前，最有效的素因子分解方法的運算量大約為 O(exp(cL(1/3)log(L)(2/3), 其中L為要分解的整數N的位數。 利用現有大型計算機的能力, 能夠分解的最大整數不能超過100位. 例如, 至今尚無人能分解Fermat數F_9. 讀者能否給出F_6的分解?1994年，美國數學家Peter Shor做

21、出了一項驚人的工作。他指出，如果使用量子計算機，則因子分解算法的運算量為 O(L2log(L)loglog(L).完全數 所謂完全數是指它的所有因子(除去它本身 ) 之和等于該完全數. 例如, 6是一個完全數. 因為1+2+3=6. 下一個完全數是28. 請讀者找出10000以內的所有完全數, 并對它做素因子分解. 你能據此猜測完全數的通式嗎? 完全數與Mersenne素數有何聯系? 你能由此找到更多的完全數嗎? 是否存在奇完全數? 完全數是否有無窮多個?除6以外, 完全數都有一個奇妙的特性, 就是每個完全數可以表為幾個連續(xù)的奇數之立方和. 如28=13+23. 請你對你找出的完全數驗證此特性.完全數的另一個特性是它的因子的倒數和為1。如 1/2+1/3+1/6=1。把完全數（除6）各位數相加得另一數，這樣一直做下去，最后得1。完全數二進制形式為：111000孿生素數