米勒-拉宾检验

要測試 $N$ 是否為質數，首先將 $N-1$ 分解為 $2^s d$。在每次測試開始時，先隨機選一個 介於 $[1, N-1]$的整數 $a$，之後如果對所有的 $r \in [0, s-1]$，若$a^d \mod N \neq 1$ 且 $a^{2^{r}d} \mod N \neq -1$，則 N 是合數。否則，$N$ 有 $3/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;

参见

• 卢卡斯-莱默检验法
• 埃拉托斯特尼筛法
• 试除法
• 费马素性检验