質數的定義:一個大於1的整數中,除了1和此整數自身外,沒法被其他數整除的自然數;即是只有兩個正因數(1和自己)的自然數。比1大但不是質數的數稱之為合數又稱合成數,而1和0既非質數也非合數。質數的屬性稱為素性,質數在數論中有著非常重要的地位。(出自維基百科)
很久很久以前我聽過一則新聞,科學家利用電腦運算找出目前最大的質數,據說報紙得用上好幾張才能把數字給寫完。
雖然我不念數學,但如果以上新聞是真,那麼顯然到目前為止質數找不到規律性。但它是否真的沒規律?在未來日子裡人類是否可以找到個公式去預測它存在?在哪裡存在?
我打賭一定有數學家這樣想過,雖然這任務難比登天。
昨天聽說Many大大的一位同學即將步入禮堂,這讓我頗感興趣,究竟是誰那麼厲害可以征服那所綠色制服的畢業生。沒想到是位三十五歲的上班族。我詫異的質問:「那怎麼認識的?」
「聯誼時啊。」
「什麼?原來北一女尬意這一套。那我明天就去報名聯誼團。」猜了好幾年原來她們尬意相親這個古早味。
「你還真是不死心。她不念北一女,是我國小同學啦。」
「唉,早說好嗎?真是的。幫我跟她說聲祝你幸福。」
「你對北一女還真是不死心。北一女各個學生都很有特色。唯一相同之處大概只有制服吧。」
「或許吧。可是我就是想找出你們的規律性。」其實我原本想加上你們好歹都有XX性染色體等諸如此類女性固有特徵之類的話語,但想想還是算了。
「就跟質數一樣。總有數學家想去找出它的規律性。」我繼續替自己辯解著。
是啊,就跟質數一樣,總有數學家想找出它的規律性。但試問?有誰找到?我們對質數的定義再清楚不過了,還不就是那麼一回事。但不論它是否真有規律性,很顯然數千年來所有嘗試努力的數學家全失敗了。
它是否有規律性依然是個謎。你知道它一直存在,但除了一個個除除看竟然找不到一個更好的方法去證明它存在。(即使使用牛頓法依然得花不少時間…)
我對北一女的定義也十分清楚,還不就是那麼一回事,但至今已經好幾年過去,我依舊找不到她們的規律性。
北一女好比質數,即使我清楚她的定義,即使我明瞭她的特性,但我終究找不到她的規律…
認識很多北一女好比我知道1、3、5、7是質數一樣,根本對研究也沒啥幫助。
所以該換個研究題目了,不然一直拿不到博士文憑無法畢業也是難過…
人類行為並非不科學,而是我們的科學還不足以預測它…
所以文學有其不可取代性…(發牢騷真的非常好用…)
PS.補充資料(出自維基百科)
尋找質數
尋找在給定限度內的質數排列,埃拉托斯特尼篩法法是個很好的方法。然而在實際中,我們往往是想知道一個給定數是否是質數,而不是生成一個質數排列。進而,知道答案是很高的機率就是已經很滿意的了,用素性測試迅速地檢查一個給定數(例如,有幾千位數的長度)是否是質數是可能的。典型的方法是隨機選取一個數,然後圍繞著這個數和可能的質數N檢查一些方程式。重複這個過程幾次後,它宣佈這個數是明顯的合數或者可能是質數。這種方法是不完美的:對某些測試而言,例如費馬測試,不論選取了多少隨機數都有可能將一些合數判斷成可能的質數,這就引出了另一種數偽質數。而像米勒-拉賓測試,雖然只要選取夠多數字來檢驗方程式,就可以保證其檢驗出的質數性是正確的,但這個保證門檻的數量太過龐大,甚至比試除法所需的 還要多,在有限時間內運行起來只能知道答案正確的機率很高,不能保證一定正確。
目前最大的已知質數是230402457 − 1(此數字位長度是9,152,052),它是在2005年12月15日由GIMPS發現。這組織也在2005年2月18日發現了目前所知第二大的已知質數225964951 - 1(此數字位長度是7,816,230)。
數學家一直努力找尋產生質數的公式,但截至目前為止,並沒有一個基本函數或是多項式可以正確產生所有的質數。歷史上有許多試驗的例子:17世紀初法國數學家梅森(Mersenne)在他的一個著作當中討論了這樣一種我們現在稱之為梅森質數的質數,Mp=2p - 1,本來以為只要p是一個質數,n = 2p - 1就會是一個質數,這在p = 3,p = 5,p = 7都是正確的,但是p = 11時 }-就不是質數了。
檢驗質數
檢查一個正整數N是否為質數,最簡單的方法就是試除法,將該數N用小於等於 的所有質數去試除,若均無法整除,則N為質數。
2002年,印度人 M. Agrawal 、N. Kayal 以及 N. Saxena 提出了 AKS 質數檢驗演算法,證明了可以在多項式時間內檢驗是否為質數。
文章定位: