米勒-拉宾检验

维基百科,自由的百科全书
跳转至: 导航搜索

米勒-拉賓質數判定法是一种質數判定法則,利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授 Gary Lee Miller 首先提出了基于广义黎曼猜想确定性算法,由于广义黎曼猜想并没有被证明,其后由以色列耶路撒冷希伯來大學Michael O. Rabin教授作出修改,提出了不依赖于该假设的随机化算法

概念[编辑]

要測試 N 是否為質數,首先將 N-1 分解為 2^s d。在每次測試開始時,先隨機選一個 介於 [1, N-1]的整數 a,之後如果對所有的 r \in [0, s-1],若a^d \mod N \neq 1a^{2^{r}d} \mod N \neq -1,則 N 是合數。否則,N3/4機率質數

示例代码[编辑]

下面是根据以上定义而使用 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;

参见[编辑]