跳至內容

米勒-拉賓質數判定法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

米勒-拉賓質數判定法(英語:Miller–Rabin primality test)是一種質數判定法則,利用隨機化算法判斷一個數是合數還是可能是質數。1976年,卡內基梅隆大學的計算機系教授蓋瑞·米勒英語Gary Miller (computer scientist)首先提出了基於廣義黎曼猜想確定性算法,由於廣義黎曼猜想並沒有被證明,於1980年,由以色列耶路撒冷希伯來大學麥可·拉賓教授作出修改,提出了不依賴於該假設的隨機化算法

概念

首先介紹一個相關的引理。我們發現 總是得到 ,我們稱 的「平凡平方根」,當 是質數且 時,不存在 的「非平凡平方根」。為了證明該引理,首先假設 的平方根之一,於是有

也就是說,質數 能夠整除 或者 ,根據歐幾里得引理, 或者 能夠被 整除,即 ,

的平凡平方根。

現在假設 是一個質數,且 。於是 是一個偶數,可以被表示為 的形式, 都是正整數且是奇數。對任意在 範圍內的 ,必須滿足以下兩種形式的一種:

其中 是某個滿足 的整數。

因為由於 費馬小定理 ,對於一個質數 ,有

又由於上面的引理,如果我們不斷對取平方根後,我們總會得到 。如果我們得到了 ,意味着②式成立, 是一個質數。如果我們從未得到 ,那麼通過這個過程我們已經取遍了所有 的冪次,即①式成立。

米勒-拉賓質數測試就是基於上述原理的逆否,也就是說,如果我們能找到這樣一個 ,使得對任意以下兩個式子均滿足:

那麼 就不是一個質數。這樣的 稱為 是合數的一個憑證(witness)。否則 可能是一個證明 是質數的「強偽證」(strong liar),即當確實是一個合數,但是對當前選取的 來說上述兩個式子均不滿足,這時我們認為是基於的大概率質數。

每個奇合數 都有很多個對應的憑證 ,但是要生成這些 並不容易。當前解決的辦法是使用概率性的測試。我們從集合 中隨機選擇非零數 ,然後檢測當前的 是否是 為合數的一個憑證。如果 本身確實是一個合數,那麼大部分被選擇的 都應該是 的憑證,也即通過這個測試能檢測出 是合數的可能性很大。然而,仍有極小概率的情況下我們找到的 是一個「強偽證」(反而表明了 可能是一個質數)。通過多次獨立測試不同的 ,我們能減少這種出錯的概率。

對於測試一個大數是否是質數,常見的做法隨機選取基數,畢竟我們並不知道憑證和偽證在這個區間如何分佈。典型的例子是 Arnault 曾經給出了一個397位的合數,但是所有小於307的基數都是是質數的「強偽證」。不出所料,這個大合數通過了 Maple 程序的isprime() 函數(被判定為質數)。這個函數通過檢測 這幾種情況來進行質性檢驗。

例子

假設我們需要檢驗 是否是一個質數。首先,於是我們得到了.我們隨機從中選取,假設,於是有:

因為我們得到了一個 -1,所以要麼確實是一個質數,要麼是一個「強偽證」。我們再選取,於是有:

為合數的一個憑證,而是一個「強偽證」。

選取特定的整數可以在一定範圍內確定(而非單純基於概率猜測)某個整數是質數還是合數。對於小於的情形,選取共三個憑據可以做到這一點;對於小於的情形,選取共七個憑據可以做到這一點[1]

算法複雜度

這一算法可以被表示成如下偽代碼

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]
   xad mod n
   if x = 1 or x = n − 1 then
      continue WitnessLoop
   repeat r − 1 times:
      xx2 mod n
      if x = n − 1 then
         continue WitnessLoop
   return composite
return probably prime

使用模冪運算,這個算法的時間複雜度是是我們測試的不同的 的值。也就是說,這是一個高效的多項式時間算法。使用快速傅立葉轉換能夠將這個時間推進到 O(k log2n log log n log log log n) = Õ(k log2n).

如果我們加入最大公因數算法到上述算法中,我們有時候可以得到 的因數,而不僅僅是證明 是一個合數。例如,若 是一個基於 的可能的質數,但不是一個大概率質數,則將得到 的因數。如果因式分解是必要的,這一算法可以加入到上述的算法中,代價是增加了一些額外的運算時間。

例如,假設 ,則.於是,這也告訴我們 不是一個大概率質數,即 是一個合數。如果這個時候我們求最大公因數,我們可以得到一個的因數:.這時可行的,因為是一個基於2的偽質數,但不是一個「強偽質數」。

示例代碼

下面是根據以上定義而使用Magma語言編寫的「米勒-拉賓」檢驗程序。

function ModPotenz(a,b,n)
erg:=1;
while (b ne 0) do
       b, rest:=Quotrem(b,2);
       if (rest ne 0) then erg:=((erg*a) mod n); end if;
       a:= (a^2 mod n);
     end while;
     return erg;
end function;
;
function Miller_rabin(n)
  if (n mod 2 ne 0) then
  d:=n-1; s:=0;t:=50;
  while (d mod 2) eq 0 do
    d:=d div 2;
    s:=s+1;
  end while;
  k:=0;
  while(k lt t) do
    a:=Random(1,n-1);
    k:=k+1;
    if GCD(a,n) ne 1 then
      continue;
    end if;
    x:=ModPotenz(a,d,n);
    if(x ne 1) then
      for r in [0,s-1] do
        x:=ModPotenz(a,2^r*d,n);
        if(x eq (n-1)) then
           return "probably prime";
        end if;
      end for;
    elif (x eq 1) then
      break;
    end if;
  end while;
  end if;
  return "composite";
end function;

參見

參考資料

  1. ^ Deterministic variants of the Miller-Rabin primality test. [2019-11-01]. (原始內容存檔於2012-07-11).