米勒-拉賓素性檢驗(米勒-拉賓檢驗)

米勒-拉賓素性檢驗

米勒-拉賓檢驗一般指本詞條

米勒-拉賓素性檢驗是一種素數判定法則,利用隨機化算法判斷一個數是合數還是可能是素數。卡內基梅隆大學的計算機系教授Gary Lee Miller首先提出了基於廣義黎曼猜想確定性算法,由於廣義黎曼猜想並沒有被證明,其後由以色列耶路撒冷希伯來大學的Michael O. Rabin教授作出修改,提出了不依賴於該假設的隨機化算法

基本介紹

  • 中文名:米勒-拉賓素性檢驗
  • 外文名:Miller-Rabin prime test
  • 定義:素數判定法則
  • 相關術語隨機化算法
  • 學科:密碼學
  • 領域:密碼學
概念,例子,算法複雜度,

概念

首先介紹一個相關的引理
總是得到1,稱這兩個數為1的“平凡平方根”。當p是素數且p>2時,不存在
的“非平凡平方根”。為了證明該引理,我們假設x是
的平方根,於是有
推出p|(x+1)(x-1),也就是說,p|x+1或p|x-1。
現在假設n是一個奇素數,且 n>2。於是n-1是一個偶數,可以被表示為
的形式,s和d都是正整數且d是奇數。對任意在
範圍內的a 和
,必滿足以下兩種形式的一種:
因為由於費馬小定理,對於一個素數n,有
又由於上面的引理,如果我們不斷對
取平方根,我們總會得到 1 或 -1。如果我們得到了 -1,意味著②式成立,n是一個素數。如果我們從未得到 -1,那么通過這個過程我們已經取遍了所有2的冪次,即①式成立。
米勒-拉賓素性測試就是基於上述原理的逆否,也就是說,如果如果我們能找到這樣一個a,使得對任意
以下兩個式子均滿足:
那么n就不是一個素數。這樣的a稱為n是合數的一個憑證(witness)。否則a可能是是一個證明n是素數的“強偽證”(strong liar),即當n確實是一個合數,但是對當前選取的a來說上述兩個式子均不滿足,這時我們認為n是基於a的大機率素數。
每個奇合數n都有很多個對應的憑證a,但是要生成這些a並不容易。當前解決的辦法是使用機率性的測試。我們從集合
中隨機選擇非零數a,然後檢測當前的a是否是n為合數的一個憑證。如果n本身確實是一個合數,那么大部分被選擇的a都應該是n的憑證,也即通過這個測試能檢測出n是合數的可能性很大。然而,仍有極小機率的情況下我們找到的a是一個“強偽證”(反而表明了n可能是一個素數)。通過多次獨立測試不同的a,我們能減少這種出錯的機率。
對於測試一個大數是否是素數,常見的做法隨機選取基數a,畢竟我們並不知道憑證和偽證在 [1,n-1]這個區間如何分布。典型的例子是 Arnault 曾經給出了一個397位的合數n,但是所有小於307的基數a都是n是素數的“強偽證”。不出所料,這個大合數通過了 Maple 程式的isprime()函式(被判定為素數)。這個函式通過檢測 a=2,3,5,7,11這幾種情況來進行素性檢驗。

例子

假設我們需要檢驗n=221是否是一個素數。首先
,於是我們得到了 s=2和d=55。我們隨機從[1,n-1]中選取a,假設a=174,於是有:
因為我們得到了一個 -1,所以要么n=221確實是一個素數,要么a=174是一個“強偽證”。我們再選取a=137,於是有:
即a=137是n=221為合數的一個憑證,而a=174是一個“強偽證”。

算法複雜度

這一算法可以被表示成如下偽代碼
Input #1: n > 3, an odd integer to be tested for primality;
Input #2: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2r·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
pick a random integer a in the range [2, n − 2]
x ← ad mod n
if x = 1 or x = n − 1
then
continue WitnessLoop
repeat r − 1 times:
x ← x2 mod n
if x = 1
then
return composite
if x = n − 1
then
continue WitnessLoop
return compositereturn probably prime
使用模冪運算,這個算法的時間複雜度是
,k是我們測試的不同的a的值。也就是說,這是一個高效的多項式時間算法。使用快速傅立葉變換能夠將這個時間推進到O(klognlog lognlog log logn) =Õ(klogn).
如果我們加入最大公因數算法到上述算法中,我們有時候可以得到n的因數,而不僅僅是證明n是一個合數。例如,若n是一個基於a的可能的素數,但不是一個大機率素數,則
將得到n的因數。如果因式分解是必要的,這一GCDs算法可以加入到上述的算法中,代價是增加了一些額外的運算時間。
例如,假設n=341,則n-1=340=85*4。於是
,這也告訴我們n不是一個大機率素數,即n是一個合數。如果這個時候我們求最大公因數,我們可以得到一個n=341的因數:
。這是時可行的,因為n=341是一個基於2的偽素數,但不是一個“強偽素數”。

相關詞條

熱門詞條

聯絡我們