跳转到内容

米勒-拉宾检验

本页使用了标题或全文手工转换
维基百科,自由的百科全书
(重定向自米勒-拉賓檢驗

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