素數的尋找?這是一系列關于數論的介紹性文章，目的在于推廣數學知識，拓展讀者的數學思維至于為什麼用圖文而不是視頻？圖文有三個優越性：一是圖文數據量小，節省學習時間；二是有助于個人主動思考；三是文字裡的關鍵字，可以方便讀者查閱相關資料，今天小編就來聊一聊關于素數的尋找?接下來我們就一起去研究一下吧!

素數的尋找

這是一系列關于數論的介紹性文章，目的在于推廣數學知識，拓展讀者的數學思維。至于為什麼用圖文而不是視頻？圖文有三個優越性：一是圖文數據量小，節省學習時間；二是有助于個人主動思考；三是文字裡的關鍵字，可以方便讀者查閱相關資料。

素數是整數的基本構件，并且有無窮多素數。小素數可以通過簡單計算驗證，如何判别一個大整數是不是素數，是個不容易的事情。

例如，對大素數

m = 113 736 947 625 310 405 231 177 973 028 344 375 862 964 001

與

n = 113 736 947 625 310 405 231 177 973 028 344 375 862 953 603,

利用嘗試法，驗證直至這個平方根的所有可能因數，工作量太大。将數自乘按非常大的數取模的非常高的幂次則不太困難，這些工作，對計算機更容易。

= 39 241 970 815 393 499 060 120 043 692 630 615 961 790 020(mod m)

費馬小定理告訴我們，如果p是素數，則對每個整數a，因此，若 不與2(mod m)同餘，m肯定不是素數。

我們已證明m不是素數，盡管不知道如何分解m。m是合數的證明确實沒有提供任何能幫助我們尋求因數的線索。這告訴我們常常無需分解一個數就可得知它為合數。

考慮數

n = 113 736 947 625 310 405 231 177 973 028 344 375 862 953 603.

進行類似計算，求得

這裡不能判斷n是合數，利用費馬小定理，我們可以判定一個數不是素數，卻不能判斷它是合數。

用更多的數，來驗證n是不是素數，

我們仍不能用費馬小定理得到n是素數的結論。但是，對a的99個不同值，暗示n是“可能”素數。

這是個很奇怪的斷言，一個數怎樣能成為“可能素數”呢？要麼是素數要麼不是素數。 假設我們将數n看作一種自然現象，并用試驗科學家的精神研究n。通過選取數a的不同值并計算的值進行試驗。如果單個試驗産生甚至除a外的任何數，則得到n肯定是合數的結論。所以，有理由相信每次進行試驗确實會得到我們收集n是素數的“證據”的數值a。

總結一下，通過觀察a的n次幂不等于a的那些值，我們可在堅實的基礎上進行這種推理。如果，我們說數a是n的證據。如果n是素數，則顯然沒有證據。

有一種奇怪的合數，它們不存在證據，比如561。1910年卡米歇爾注意到了這個現象，,所以用卡米歇爾來命名這種數。卡米歇爾數是這樣的合數n，即對每個整數，都有

卡米歇爾數是可冒充素數的一種合數，因為它沒有合數特征的證據。我們已看到561是卡米歇爾數，事實上它是最小的卡米歇爾數。下面是直到10000的所有卡米歇爾數的完全列表:561, 115, 1729, 2465, 2821, 6601, 8911。

卡米歇爾數有兩個性質：

(A) 每個卡米歇爾數是奇數。

(B)每個卡米歇爾數是不同素數的乘積。

卡米歇爾數的兩個性質(A)與(B)是有用的，有下述的卡米歇爾數判别法。

定理 (卡米歇爾數的考塞特判别法) 設n是合數，則n是卡米歇爾數當且僅當它是奇數，且整除n的每個素數p滿足下述兩個條件：

(1)不整除n.

(2)p-1整除n -1.

卡米歇爾數的存在，需要一個更好的檢驗合數的方法，目前有拉賓-米勒測試。

拉賓-米勒測試基于素數的以下性質。

定理 (素數的一個性質) 設p是奇素數，記

q是奇數.

設a是不被p整除的任何數，則下述兩個條件之一成立：

(i)模p餘1.

(ii) 數之一模p餘-1.

轉到開頭素數的性質，我們得到被稱為拉賓-米勒測試的合數試驗。如果n是奇素數，且n沒有前面的素數性質，則它必是合數；對a的許多不同值，如果n确實具有素數性質，則n可能是素數。

定理 (合數的拉賓一米勒測試) 設n是奇素數，記n-1=，q是奇數。對不被n整除的某個a，如果下述兩個條件都成立，則n是合數。

(a)

(b) 對所有, .

對a的任何特别的選取，拉賓-米勒測試結論性地證明n是合數，也揭示出n可能是素數。n的合數性的拉賓一米勒證據是拉賓一米勒測試成功證明n是合數的數a。拉賓一米勒測試如此有用的理由歸于下述事實。

如果n是奇合數，則1與n-1之間至少有75%的數可作為n的拉賓一米勒證據。

換句話說，每個合數有許多拉賓-米勒證據來說明它的合數性。所以，不存在拉賓-米勒測試的任何“卡米歇爾型數”。

舉個例子，用a=2的拉賓-米勒測試應用到卡米歇爾數561。n-1 = 560 = ，計算

,，

第一個數既不是1，也不是-1，其他數也不是-1，所以2是561為合數的事實的拉賓-米勒證據。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!