<2> 有限時間内，計算一個盡可能大的素數

1 . 問題點： “ 有限時間 ”、“ 盡可能大”、“ 素數 ”

“素數“  ：需要經過素性測試合格後的數字

“有限時間”：測試一個數字，可接受的時間内，并非無窮盡的依靠暴力求解

“盡可能大”：可檢測數的上限

2 . 問題點求解

2 . 1 “ 素 數 ”

1） 概 念： 大于 1 的自然數中，除了 1 和它本身以外不再有其他因數的數稱為質數，   

素數有無限個。

2） 素性測試待測方法：

方法一： 根據定理檢測    （真 素 數 測 試）

方法二： 改進版定理檢測  （真 素 數 測 試）

方法三： 一般篩選法      （真 素 數 測 試）

方法四： 改進版篩選法    （真 素 數 測 試）

方法五： Miller Rabin 算法（概 率 素 數 測 試）

2 . 2 “ 有 限 時 間 ”

1） 待測方法介紹

· 根據定理檢測

顧名思義，這種方法是根據概念進行試除計算，即：一個數字僅能被 1 和本身

整除。若存在其他數字可以整出此數字，則為合數，反之為素數（質數） 。

優點 : 易了解素數概念

缺點 : 每對一個數字進行素性測試，都需要從 2試除至待測數字的上一個數

字，效率低下。

· 改進版定理檢測

根據概念，是否為素數，是判斷存在數字能整除待測數字（1 和本身除外）。而一旦存在此數字，由于數字是成對出現，是以隻需要判斷數字對中最小的一個數字即可。得到：“ 任意一個數的最大質因數都小于或等于這個數的平方根 ”。是以，在對待測數字進行素性測試時，僅需要從 2 試除至待測數字的平方根即可，可以減少一些測試時間。

優點 : 能稍微減少一些測試時間

缺點 : 每對一個數字進行素性測試，都需要從 2試除至待測數字的平方根，效

率依然低下。

· 一般篩選法

我們知道，2 是素數，可以得出，2的倍數都是合數。我們還知道，3 是素數，可以得出，3 的倍數也都是合數。有：“ 素數的倍數都是合數 ”是以根據以上，我們可以通過幾個初始的素數表，找到所有的合數，并将素數篩選出來。

優點 : 能大幅減少測試時間

缺點 : 依然對于很多數字進行重複篩選，影響效率。

· 改進篩選法

例如：需要找 100 之内的素數，對于 30 這個數字 : 

30= 2 X 15

30 既是 2 的倍數，也是 15 的倍數，是以在一般的篩選法的過程中，30 在 2 的時候被篩選一次，在 15 的時候會被再次篩選一次。當數量級較大時，這種情況就會十分影響效率。是以，在改進的篩選方法中，這種情況應被避免，可以更大幅度的減少測試時間。

優點 : 繼續大幅減少測試時間

缺點 : 存在記憶體洩漏風險。

· Miller-Rabin 算法

Miller-Rabin 算法是一種基于機率的素性測試算法，是以該算法與一般的基于事實的真素性測試方法的差別是：存在一定的誤判率。但是在對于某個較大的待測數字進行多次測試的情況下，誤判率可以控制在可忽略範圍内。Miller-Rabin 算法基于 Fermat 算法，屬于後者的變形、改進。首先引入 Fermat 定理：n是一個奇素數，a是任何整數(1≤ a≤n-1) ，則a^(n-1)≡1(mod n)根據此定理可以知道，對于給定的待測數字 n，可以通過設定素性測試算法，計算 w = a^(n-1)%n 的結果來判定。

W!=1，n一定不是素數；

W==1，n可能是素數；

再引入二次探測定理，如果 n 是一個整數，且 0<x<n，則：x2%p=1 有： x= 1 / x = p-1。若n是素數,則 ( n-1 ) 一定是偶數,是以可令(n-1)=m*(2^q),其中m是正奇數( 若n是偶數,則上面的m*(2^q)一定可以分解成一個正奇數乘以2的k次方的形式 ),q是非負整數。

借助 Fermat 定理，進行如下測試：a^(m)%n、a^(2m)%n、a^(4m)%n、a^（m*(2^q)）%n。進行這些測試的過程為：Miller-Rabin 測試。

誤判率：若 n 是素數,a 是小于 n 的正整數,則 n 對以 a 為基的Miller 測試,結果為真。Miller 測試進行 k次,将合數當成素數處理的錯誤機率最多不會超過 4(-k)。

算法：輸入：大于 3 的奇整數 n 和大于等于 1 的安全參數 t（測試幾輪）傳回：是否是素數

1  .把 n-1 表示為：2s * r 

2  .對 i 從 i 到 t 做如下操作：

3  .選擇一個随機整數 a(2<=a<=n-2)

4  .計算 y = a*r mod n

5  .如果 y≠1 并且 y ≠n-1 作下面的操作,否則轉 3：

5.1     j←1；

5.2     當 j≤s-1 并且 y≠n-1 循環作下面操作,否則跳到 5.3；計算 y ←y2 mod n;如果 y=1 傳回合數；否則 j←j+1；

5.3     傳回素數

優點 : 對于大數能對其素性進行有效檢測，廣泛用于密碼學等安全領域缺點 : 檢測速度受限

 2） 比 較

測試條件：

作業系統：Windows 10

處理器：Intel(R) Core(TM) i5-4460 CPU @3.20GHz 3.20 GHz 記憶體：4.00 GB                      

系統類型： 64 位作業系統運作模式： Debug 下

· 1 億級檢測時間對比（機關：秒（s），表 2-2-1）

素性檢測                1                   2                        3                     平均

根據定理檢測 改進定理檢測 一般篩選法 改進篩選法 Miller Rabin	/	/	/	/
196.855	196.709	194.882	196.149
4.884	4.338	4.408	4.543
1.303	1.204	1.227	1.245
( 大數 )	( 大數 )	( 大數 )	( 大數 )

                                                                   表 2-2-1

 · 時 間 複 雜 度（ 表 2-2-2 ）

 素性檢測                                                 時間複雜度

根據定理檢測 改進定理檢測 一般篩選法 改進篩選法 Miller Rabin	O(n)，随着問題規模上升急劇上升
O(√n)，随着問題規模上升急劇上升
O(n)，優化得當可達線性篩選
O(n)，優化得當可達線性篩選
O(log32 (n))，最壞

                                                                    表 2-2-2

2 . 3 “ 盡可能大 ”

· 資料類型（表 2-3-1）

資料類型                              最小值                                    最大值

int unsigned int long unsigned long long long unsigned long long __int64 unsigned __int64	-2147483648	2147483647
4294967295
-2147483648	2147483647
4294967295
-9223372036854775808	9223372036854775807
18446744073709551615
-9223372036854775808	9223372036854775807
18446744073709551615

                                                                     表 2-3-1

根據表 2-3-1，常用資料類型的最大值為“18446744073709551615 ”，資料類型為unsigned long long或unsigned __int64，依然是有限的，雖然素數是無限的，但是目前常用的資料類型的範圍跟素數的範圍依然遠遠不在一個數量級。并且在大數的素性測試中，普通的測試方法依然是能力有限，是以針對相對比較大（10億級别以上）的數字采用Miller-Rabin 算法，而相對較小的數字（10 億級别以下）采用改進版的篩選法。

理論上，有限時間内，Prime 程式可輸出的素數最大可以到 263 ~ 265之間。

3 . 其 他

· 算法

Prime程式的 Millmer-Rabin 算法在測試輪數的合理安排下，對一個大數素性測試，可以達到 99%左右的識别率， 是以認為是可靠的算法。

· 大數

素性測試雖然沒有問題，但是在“大數”的生成方面依然受限于資料類型。假設存在：int a[2017]，而 a[0]可以存儲的數字最大為 2147483647。同理，a[1]至 a[2016]每個數組元素存儲的最大數字為 2147483647。那麼，數字“1102147483647”可以被寫成“a[1] 合并 a[0]”即： a[1] = 110 , a[0] = 2147483647根據以上，則 a[2017]可以合并存儲的數字最大為“ 231 次方的 2017 次方 ”。是以，大數生成方式以及自定義大數運算與素性測試結合是程式需要改進的部分。

注意：需要目标機處于 64 位 Windows 系統下。

參 考

[1]曽加：如何程式設計最快速度求出兩百萬以内素數個數（不限語言和算法）？[DB/0L].

ZhiHu,2014[2017].https://www.zhihu.com/question/24942373

[2]LCCN:sh85093218,GND:4047263-2,NDL:00571462: Prime

number[G/OL].Wikipedia,2017[2017]. https://en.wikipedia.org/wiki/Prime_number[3]Unknown author : Miller-Rabinprimality test.Wikipedia,2016[2017].

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

[4]nash_:素性測試[DB/OL].CSDN,2013[2017].

http://blog.csdn.net/zmazon/article/details/8290774