今天第一次寫(xiě)出miller-rabbin素?cái)?shù)測(cè)試，知道這個(gè)概率算法對(duì)于大整數(shù)測(cè)試是否是素?cái)?shù)十分有效，成功率有保證~于是突然想到有沒(méi)有手機(jī)號(hào)是素?cái)?shù)！
電腦開(kāi)了半個(gè)小時(shí)，用miller-rabbin測(cè)試，CPU一直保持占用率100%，結(jié)果搜結(jié)束之后我的data.out里面還是什么都沒(méi)有！
拿出紙筆，開(kāi)始計(jì)算：如果手機(jī)號(hào)只有如下幾個(gè)限制：1、以1開(kāi)頭；2、共11位。根據(jù)素?cái)?shù)定理，手機(jī)號(hào)是素?cái)?shù)的概率為0.04（以1開(kāi)頭的11位整數(shù)大約有4億個(gè)是素?cái)?shù)）。
很明顯，miller-rabbin出錯(cuò)了！用5000-10000之間的素?cái)?shù)對(duì)拍了一下，算法沒(méi)有出錯(cuò)。毫無(wú)疑問(wèn)，快速冪取模時(shí)溢出了！
換用O(n^0.5)的素?cái)?shù)判斷，很快找到了許多素?cái)?shù)手機(jī)號(hào)，列出幾個(gè)好的手機(jī)號(hào)吧：

15956880001；

15956880007；

15256880101；

15256888811；

15256885577

還有很多……