Miller Rabin算法

是一個素數，那么Z(n )中的元素叫作合數n 是一個合數，如果a不屬於W(n

簡介

Miller-Rabin算法是目前主流的基於機率的素數測試算法，在構建密碼安全體系中占有重要的地位。通過比較各種素數測試算法和對Miller-Rabin算法進行的仔細研究，證明在計算機中構建密碼安全體系時， Miller-Rain算法是完成素數測試的最佳選擇。通過對Miller-Rabin 算 法底層運算的最佳化，可以取得較以往實現更好的性能。
隨著信息技術的發展、網路的普及和電子商務的開展， 信息安全逐步顯示出了其重要性。信息的泄密、偽造、篡改 等問題會給信息的合法擁有者帶來重大的損失。在計算機中構建密碼安全體系可以提供4種最基本的保護信息安全的服 務：保密性、數據完整性、鑑別、抗抵賴性，從而可以很大 程度上保護用戶的數據安全。在密碼安全體系中，公開密鑰 算法在密鑰交換、密鑰管理、身份認證等問題的處理上極其有效，因此在整個體系中占有重要的地位。目前的公開密鑰 算法大部分基於大整數分解、有限域上的離散對數問題和橢 圓曲線上的離散對數問題，這些數學難題的構建大部分都需 要生成一種超大的素數，尤其在經典的RSA算法中，生成的素數的質量對系統的安全性有很大的影響。目前大素數的生 成，尤其是隨機大素數的生成主要是使用素數測試算法，本 文主要針對目前主流的Miller-Rabin 算法進行全面系統的分析 和研究，並對其實現進行了最佳化。

機率素數測試算法和真素數測試算法

素數測試算法主要分兩種：機率素數測試算法和真素數測試算法。 機率素數測試算法的特點是：算法速度較快、原理簡單、易於編程實現、有一定的誤判機率。與之相比，真素數 測試算法最大的特點是不存在誤判，但從套用角度講，真素 數測試算法不如機率測試算法實用。最大的原因是：真素數 測試算法相對較慢。一些較快的真素數測試算法是針對某些特定類型的數設計的，如 ： Lucsa-Lehmer 算法是針對 Mersenne數的測試算法，這類素數測試算法在密碼學中的應 用很受限制。基於橢圓曲線和割圓環的真素數測試算法可以 用來測試任意的隨機數，但這兩類算法都很慢，目前最好的基於橢圓曲線的算法的時間複雜度是log n6+ ε(ECPP)，基於 割圓環的測試算法的時間複雜度log nclogloglogn。
真素數測試算法背後的理論比較艱深，在計算機中的實 現十分複雜，實現複雜帶來的不正確實現的安全隱患要比機率算法誤判帶來的安全隱患大得多。機率算法的誤判完全可以被控制在一個極低的可接受的機率範圍內，例如：控制誤 判機率在(1/2)80以下足可以滿足絕大部分的安全需求(密碼學 的套用中不存在絕對的0誤差，軟、硬體實現中的各種不安全因素遠遠大於機率算法的誤判)，加之機率算法速度快並 且實現相對容易，因此在實際套用中，大多使用基於機率的 素數測試算法。

基於機率的素數測試算法的基本框架

目前的基於機率的素數測試算法一般都遵循一種基本的 框架[1]。給定一個正奇數n，定義一個集合W(n)屬於集合Z(n) (Z(n)是模n的非負整數集合)並有如下屬性：
(1) 給定一個屬於集合Z(n) 的非負整數a ，可以在多項式時間複雜度內判斷a 是否屬於集合W(n) ；
(2) 如果n是一個素數，那么Z(n) 中屬於集合W(n) 的元素 的個數為0；
(3)如果n是一個合數，那么Z(n)中屬於集合W(n)的元素的個數大於等於n/2。
如果n是一個合數，那么集合W(n) 中的元素叫作合數n 的證據，集合L(n)=Z(n)－W(n)中的元素叫作合數n的偽證。 基於機率的素數測試算法的基本思路是：定義一個符合以上規則的集合W(n)，對待測整數n隨機選擇屬於集合Z(n)的元 素a，檢查a 是否屬於集合W(n)，如果a 屬於W(n)則可以確定n 是一個合數，如果a不屬於W(n) 則n是素數的可能性大於等於1/2。對n 隨機地選擇元素a相對獨立地作 t 輪這樣的測試，則n是素數的可能性可以被控制在 1-(1/2)t以上。

Miller-Rabin算法的理論基礎

Miller-Rabin算法是Fermat算法的一個變形改進，它的理論基礎是由Fermat定理引申而來。
Fermat 定理： n是一個奇素數，a是任何整數(1≤ a≤n-1) ，則 an-1≡1(mod n)。
Miller-Rabin 算法的理論基礎：如果n是一個奇素數， 將n-1表示成2s*r的形式(r是奇 數)，a 是和n互素的任何整數， 那么ar≡1(mod n) 或者對某個j(0≤j ≤s －1， j∈Z) 等式 a2jr ≡－1(mod n)成立。 這個理論是通過一個事實經由Fermat定理推導而來： n是一個奇素數，則方程x2 ≡ 1 mod n只有±1兩個解。

計算機 中 Miller-Rabin算法的實現

Miller-Rabin(n,t)
輸入：一個大於3的奇整數n和一個大於等於1的安全參 數t(用於確定測試輪數)。
輸出：返回n是否是素數(機率意義上的，一般誤判機率小於(1/2)80即可) 。
1、將n-1表示成2sr，(其 中 r是奇數)
2、 對i從1到 循t 環作下面的操作：
2.1選擇一個隨機整數a(2≤a ≤n-2)
2.2計算y ←ar mod n
2.3如果y≠1並且y ≠n-1作下面的操作,否則轉3：
2.3.1 j←1;
2.3.2 當j≤s-1 並且y≠n-1循環作下面操作,否則跳到 2.3.3：
{計算y ←y2 mod n;
如果 y=1返回 "合數 "；
否則 j←j+1; }
2.3.3如果y ≠n-1 則返回" 合數" ；
3、返回"素數"。 說明：本算法2.3.2循環中的"y=1返回"合數" "是基於如下定理：
定理： 設x、y和n是整數，如果x2=y2 (mod n) 但x ≠±y
(mod n)，則(x-y)和n的公約數中有n的非平凡因子。 在算法2.3.2循環中，如果y=1則a2(j-1)r =1(mod n)，而由此也可知a2(j-1)r≠±1(mod n) ，由此通過上面的定理可以知道，(a2(j-1)r －1)和n有非平凡公因子，從而可判斷n是合數。

Miller-Rabin算法的誤判機率

經過獨立的t輪Miller-Rabin算法將一個合數誤判為素數的可能性不大於 (1/4)t，(正確實現的算法不會誤判素數為合 數)，這個誤判機率在基於Fermat定理的算法中是最好的。
這個誤判機率是利用下面兩個定理證明的：
定 理 1 ：設d=gcd(k,m) ，那么在有限群{g,g2,g3,?,gm=1}中(g是有限群的生成元，m是有限群的階) 有d個元素x滿足方程式xk=1。
定 理 2 ： 設p是一個奇素數，p-1=2sh(h是奇數)，那么在乘法群(Z/pZ)*中滿足方程式 x2rt=-1mod p(t是奇數 )的元素的個數是：0，如果r ≥s；2rgcd(h,t)，如果r<s。 利用這兩個定理，對算法輸入n分3種情況討論：
(1)n可以被某個素數的平方整除的時候;
(2)n是兩個不同素數的乘積的時候;
(3)n是兩個以上不同素數乘積的時候。
這樣可以證明Miller-Rabin算法的誤判機率上界。

Miller-Rabin算法的時間複雜度

Miller-Rabin算法是一個機率算法，算法的操作集中於 2.2步和2.3.2的循環中，最壞情況是2.3.2的循環沒有中途退 出，則一輪Miller-Rabin算法的最壞情況時間複雜度為 (1+O(1))log2(n)( 以模n乘法為基本操作)。如果以單精度乘法操作作為時間複雜度的衡量，則一輪最佳化的Miller-Rabin算法的最 壞情況時間複雜度為O(log32 (n) 。從時間複雜度來看Miller- Rabin算法的性能是很好的。在實際套用中，Miller-Rabin 算 法的實際執行速度也很快。

Miller-Rabin算法和其他機率測試算法比較

Miller-Rabin算法在基於Fermat定理的算法中是最優秀的，無論從誤判機率還是從速度上看，它都優於其它 Fermat 類算法，例如 ： Fermat 算法 、 Lehmann 算法、 Solovay- Strassen算法等。
Lucas 測試是Pomerance、Selfridge 和 Wagstaff 提出的一種基於Lucas序列的機率素數測試算法，該算法一輪消耗的 時間大概相當於6輪Miller-Rabin測試。一輪Lucas 的誤判機率 為4/15，該算法經過一些改進,一輪的誤判機率達到1/8。這 種算法在誤判機率和速度的權衡考慮上不如Miller-Rabin 算法。
Grantham-Frobenius 測 試(QFT) 是 Grantham 提出的基於 Frobenius機率素數和Frobenius強機率素數理論的算法，給定 一組參數(b,c)，誤判機率可以被控制在1/7710以下。時間複雜度是(3+O(1))log2(n)( 以模n乘法為基本操作)，大概相當於3輪Miller-Rabin算法。這種算法理論比較艱深，目前只停留在理論研究階段，還不適合現實套用。
Adams 和Shanks 提出了一種基於Perrin 序列的算法，他們算法的Q和I兩種情況下還沒發現偽素數，沒有考慮算法 的速度，只是就誤判機率來進行研究，他們的工作主要是側 重數學理論研究，算法目前還不適合現實套用。

Miller-Rabin算法的最佳化實現

Miller-Rabin算法最為耗時的步驟在2.2模冪操作和2.3.2 循環。對算法的最佳化實現主要集中在對這兩部分運算的優 化。對模冪操作的最佳化有兩種途徑：減少模冪算法中的模乘 操作和最佳化模乘操作。在求模冪的過程中不能先求冪最後一次求模，這樣會產生一個十分巨大的中間結果，造成實際的 不可操作，所以在求模冪的算法中用模乘代替乘法，使得中 間結果的長度不超過模的長度。對模冪算法的最佳化，我們使 用改進的滑動視窗算法結合Montgomery模乘和模平方算法。
表1給出模冪算法的比較。

模冪算法	預先計算		模平方	模乘法
	模平方	模乘法		最壞情況	平均情況
平方乘算法 滑動視窗類算法 改進的滑動視窗算法	0 1 1	0 2k -3 2k-1-1	t t-(k-1)≤次數≤t t-(k-1)≤次數≤t	t (t/k)-1 (t/k)-1	t/2 t/k(2k-1)/ 2k k ≤t/k(2 -1)/

* 模冪算法比較，其中k是視窗大小，根據情況 選擇以達到最優，t是指數的二進制位數。 最佳化的模冪算法描述：
輸入： x，e=(e tet-1?e1e0)2，其中et=1，k≥1( 視窗大小)
輸出： xe mod n
1、預計算
1.1、x1← MontMul(x， R2，n)，
x2←MontSqu(x 1， n)
1.2、對i 從1 到2k-1-1計算x2i+1←MontMul(x2i-1， x2，n)
2、A←R，i ←t
3、 當i≥ 0時作下面的操作：
3.1、如果ei=0，A←MontSqu(A ，n)，i← i-1
3.2、否則找到最長的位串eiei-1?es使得i-s+1≤k並且es=1,計算
3.2.1、A <－A2i-s+1 ， (利 用MontSqu函式計算)
3.2.2、A <－A*X(ee ...e )2 ，(利 用MontMul函式計算)
3.2.3、i ←s-1
4、A←MontMul(A ，1 ，n)
5、返回A
其中MontMul(x,y,n) 是Montgomery模乘函式，函式輸出 結果為x*y*R-1 mod n，MontSqu(x,n) 是Montgomery模平方函 數，輸出結果為x2R-1 mod n。模乘算法如果採用大整數乘法 和除法求模乘，因為涉及耗時的除法操作，所以要相對較 慢，結合大整數乘法和Barrett求模算法可以用2(n2+3n+1) 步 單精度乘法完成。使用Montgomery求模算法結合大整數乘法 算法，可以 在 2n(n+1) 步單精度乘法內完成算法。 Montgomery模平方的操作可以在3n(n+1) /2步單精度乘法內 完成，而Barrett模平方需要(3n(n+3)/2+1) 步單精度乘法。結 合改進的滑動視窗算法和Montgomery類算法，可以得到目前 非特殊情況下的最優的模冪算法。
在Miller-Rabin算法的2.3.2循環中的模平方操作我們沒有 使用Montgomery模平方算法，因為該算法給出的結果帶有R-1這個參數，在2.3.2循環中處理掉這個參數將占整個循環運 行時間中的很大部分，尤其是在循環的控制參數s 相對較小的時候。我們在這裡使用大整數平方算法結合Barrett求模算 法，2.3.2的循環最壞情況需要(s-1)(3n(n+3)/2+1)步單精度乘法。

Miller-Rabin算法在套用中的一些考慮

(i)
(ii)
p k ,1
pk , t
k 2 4 2
k 3 / 2 2 tk
for k 2
t 1 / 2 4 2 tk
(iii) p 7 k 2 5t k , t20
1 k15 / 4 27
k / 2 2 t
12 k 2
k / 4 3t
for k / 9
(iv) pk , t
t k / 4, k
1 k15 / 4 2
7
21
k / 2
2t for t
k / 4, k 21
Miller-Rabin算法的套用主要集中在構建密碼安全體系的素數生成模組中，當輸入的待測數n是很大(例如： 1024bits)的隨機數的時候，算法的誤判機率遠遠小於上面給出的理論 上的誤判機率上界。設Pk,t 代表(k=log2 n，t是測試的輪數)在 素數生成算法中套用t輪Miller-Rabin 算法給出錯誤結果的概 率，則有如上所示的誤判機率公式。
在一般的密碼安全體系中，誤判機率小於 (1/2)就可以滿足安全需求。表2給出了當p(k,t) ≤ (1/2)80的時候對應的k和t的值。
表2 k,t對應值

k	100	150	200	25	300	350	400	450	550	650	850	1300
t	27	18	15	12	9	8	7	6	5	4	3	2

在基底的選擇上，因為以2作為基底可以剔除很大部分 合數，並且對以2為底的模冪的運算很快，所以可以考慮在 套用中固定使用基底2，其它基底隨機選擇，這樣的改進可 以提高算法的運行速度。