millerrabin演算法

㈠ Miller Rabin演算法的優化實現

Miller-Rabin演算法最為耗時的步驟在2.2模冪操作和2.3.2 循環。對演算法的優化實現主要集中在對這兩部分運算的優 化。對模冪操作的優化有兩種途徑：減少模冪演算法中的模乘 操作和優化模乘操作。在求模冪的過程中不能先求冪最後一次求模，這樣會產生一個十分巨大的中間結果，造成實際的 不可操作，所以在求模冪的演算法中用模乘代替乘法，使得中 間結果的長度不超過模的長度。對模冪演算法的優化，我們使 用改進的滑動窗口演算法結合Montgomery模乘和模平方演算法。表1給出模冪演算法的比較。 模冪演算法 預先計算 模平方 模乘法 模平方 模乘法 最壞情況 平均情況 平方乘演算法滑動窗口類演算法 改進的滑動窗口演算法 011 02k -32k-1-1 tt-(k-1)≤次數≤t t-(k-1)≤次數≤t t (t/k)-1 (t/k)-1 t/2 t/k(2k-1)/ 2kk≤t/k(2 -1)/ * 模冪演算法比較，其中k是窗口大小，根據情況 選擇以達到最優，t是指數的二進制位數。 優化的模冪演算法描述：輸入： x，e=(e tet-1?e1e0)2，其中et=1，k≥1( 窗口大小)輸出： xe mod n1、預計算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 ←t3、 當i≥ 0時作下面的操作： 3.1、如果ei=0，A←MontSqu(A ，n)，i← i-13.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-14、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演算法的時間復雜度

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演算法的演算法基本框架

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

㈤ Miller Rabin演算法的概率素數測試演算法和真素數測試演算法

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

㈥ 利用Miller-Rabin演算法判斷一個數是否為素數，但是結果經常把素數判斷為合數，哪裡有問題求指點

while(init)
{j++;
修改j＋＋為j＝1，每次循環的時候j重置為1

//if(j>0&&y==1){flag=1;break;}
while(init)
{j= 1;

㈦ Miller Rabin演算法的在應用中的考慮

(i)(ii)p k ,1pk , tk 2 4 2k 3 / 2 2 tkfor k 2t 1 / 2 4 2 tk(iii) p 7 k 2 5t k , t201 k15 / 4 27k / 2 2 t12 k 2k / 4 3tfor k / 9(iv) pk , tt k / 4, k1 k15 / 4 2721k / 22t for tk / 4, k 21Miller-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，其它基底隨機選擇，這樣的改進可 以提高演算法的運行速度。

㈧ 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演算法

在《現代密碼學-原理與協議》這本書里看到過類似結論的證明. （7.38）

不過這個1/2不是針對1~n-1的整數集，而是針對1~n-1中元素構成的模n的乘法群Zn*，這個群中僅有那些滿足gcd(a, n) = 1這個條件的元素a。另外，需假設n若n為合數，則至少有一個證據證明它是合數。

需要一點群論的知識

1. 若G為有限群，假設H含有G的「1」(幺元)，且對於H中任意的a、b恆有ab屬於H，則H是G的子群

2. 若H為有限群G的真子群，則|H| <= |G/2|. （| |代表元素數)

證明：

定義Bad為乘法群Zn*中，不是"n為合數"的證據的元素的集合。（即滿足 a^(n-1) = 1 mod n）

顯然，1 屬於 Bad。

若a,b屬於Bad, 則 (ab) ^ (n-1) = a^(n-1) * b^(n-1)= 1*1 mod n =1 mod n

所以 ab 也屬於 Bad

由 1 可得 (Bad, *)是Zn*的一個子群

而因為若n為合數，則至少有一個1~n-1中的數使a^(n-1) 不等於 1 mod n，因此Bad為Zn*的真子群

再由2可得 Bad中元素數小於等於Zn*元素數的一半

那麼，反過來，Zn*中可以成為證據的元素至少佔Zn*中全體元素的1/2

維基網路Miller-Rabin的英文詞條下面的參考文獻中，他們的原始論文里有完整的對於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演算法的誤判概率上界。