米勒-拉賓質數判定法

素性測試

米勒-拉賓質數判定法(英語: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).