Miller_Rabin (米勒-拉宾) 素性测试

之前一直对于这个神奇的素性判定方法感到痴迷而又没有时间去了解。借着学习《信息安全数学基础》将素性这一判定方法学习一遍。

首先证明一下费马小定理。

　　若p为素数，且gcd(a, p)=1, 则有 a^(p-1) = 1 (mod p)

　　　　基于以下定理

　　　　　　若(a, p)=1，{x| (x, p)=1}为模p下的一个完全剩余系，则{ax| (x, p)=1}也为模p下的一个完全剩余系。

　　　　又{0, 1, 2, ... p-1}为模p下一个剩余系

　　　 因此有，

　　　　　　{a*0, a*1, a*2, ... a*(p-1)}为模p下的完全剩余系

　　　　　　又其中 a*0 = 0 (mod p), 去掉

　　　　　　取剩下p-1个，有 a*1 = k1 (mod p) a*2 = k2 (mod p) ... a*(p-1) = k_p-1 (mod p) ，其中 k1...k_p-1为 1, 2, ... p-1的一个排列。

　　　　　　因此 a*1 * a*2 ... * a*(p-1) = 1*2* ... *(p-1) (mod p)

　　　　　　　　即 a^p-1 * (p-1)! = (p-1)! (mod p)

　　　　　　又有 p为素数，故 gcd((p-1)!, p) = 1

　　　　所以同除 (p-1)!依然成立，得到费马小定理。

以下理论转自：没有代码的日子与聊聊如何检测素数与银河

Miller-Rabin检测依赖以下定理：

如果p是素数，x是小于p的正整数，且x^2 = 1 mod p，则x要么为1，要么为p-1。

简单证明：如果x^2 = 1 mod p，则p整除x^2 – 1，即整除(x+1)(x-1)，由于p是素数，所以p要么整除x+1，要么整除x-1，前者则x为p-1，后者则x为1。

以上定理说明，如果对于任意一个小于p的正整数x，发现1（模p）的非平凡平方根存在，则说明p是合数。

对于p-1，我们总可以将其表示为u2^t，其中u是奇数，t是正整数。此时：　　

$a^{p-1}=a^{u2^t}=(a^u)^{2^t}$

也就是可以通过先算出a^u，然后经过连续t次平方计算出a^(p-1)，并且，在任意一次平方时发现了非平凡平方根，则断定p是合数。

例如，560 = 35 * 2^4，所以可设u=35，t=4：

$\ 2^{35} mod 561=263 \ 263^2 mod 561=166 \ 166^2 mod 561=67 \ 67^2 mod 561=1$

由于找到了一个非平凡平方根67，所以可以断言561是合数。因此2就成为了561是合数的一个证据。

######要讨论米勒-拉宾素性测试，首先得证明一条引理（lamma）#######

若p是一个大于2的素数，那么如果一个数与1或者-1模n同余（即 x = 1 (mod p) 或者 x = -1 (mod p)），那么它就叫做1模n的一个非平凡的平方根。

而事实上，没有1模p的非平凡的平方根存在。（注：平凡根指1或-1(mod p) ，否则为非平凡根。）

证明：假设x是一个1模p的非平凡的平方根，那么就有：

$x^{2} equiv 1pmod{p}$

$left (x - 1 ight ) left ( x + 1 ight ) equiv 0pmod{p}.$

因为x是非平凡的，就有（x+1）与（x-1）和x互质，就是说(x+1)和（x-1）都不能被p整除，因此（x+1)(x-1)不能被p整除，引出矛盾。

因此，没有1模p的非平凡的平方根存在。证毕

————————关键的要来啦————————————

　　　　现在我们让n为一个奇质数，而（n-1）可以表示为2^s·d的形式其中s与d都为正整数，那么根据费马小定理, 费马素性测试的原理，以及上面已经证明的引理可知，这个问题的关键就是，若x的平方模p为1，那么x模p得为-1或1，p才有可能为素数，否则必为合数。若x的平方模p为-1，那么x模p不作要求，那么对于任何一个，2^r·d在r不断变化得过程中必须遵循上述的规则。这样就得出了米勒-拉宾素性测试的算法：

%%%%%%%%米勒-拉宾素性测试的算法%%%%%%%%%%

判断一个数p是否为素数（p首先得为大于等于2的正整数才有可能为素数），首先判奇偶，若为偶数只有2为素数，若为奇数（这里可以考虑去掉 3甚至5的倍数），则先求出d。对于每一个底a，让d不断乘以2直到为(p-1)/2，在此过程中（包括原本的d与d=(p-1)/2时的情况），设t为 a的d次方模p的余数，（1）当t=-1时跳出，声明p有可能为素数（2）当t=1时，若d为奇数，跳出声明p有可能为素数，否则跳出声明p必为合数（3）当d=(p-1)/2时跳出，声明p必为合数。、

————————重要的要来啦————————————

要判断n是否为素数，对于一定范围内的n，只要以一定范围内a为底就可以保证这是一个确定性算法了。下面详细：

if n < 1,373,653, it is enough to test a = 2 and 3.
if n < 9,080,191, it is enough to test a = 31 and 73.
if n < 4,759,123,141, it is enough to test a = 2, 7, and 61.
if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11.

其中前三条应该是比较用的着的，尤其是第三条，和longint是一个数量级的！非常好用！！！

Miller-Rabin primatlity test 算法能够以很高的概率来检验一个很大的数是否素数。该算法描述如下：

Input: n > 3, an odd integer to be tested for primality;
Input: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
01: write n − 1 as 2^s·d with d odd by factoring powers of 2 from n − 1
02: LOOP: repeat k times:
03: pick a randomly in the range [2, n − 2]
04: x ← a^d mod n
05: if x = 1 or x = n − 1 then do next LOOP
06: for r = 1 .. s − 1
07: x ← x² mod n
08: if x = 1 then return composite
09: if x = n − 1 then do next LOOP
10: return composite
11: return probably prime

构成该算法的思想是，如果 a ^d ≠ 1 (mod n) 以及 n = 1 + 2^s· d 是素数，则值序列

a ^d mod n，a ^2d mod n，a ^4d mod n，…，a ^{2^sd} mod n

将以 1 结束，而且在头一个 1 的前边的值将是 n – 1 (当 p 是素数时，对于 y ² ≡ 1 (mod p) ，仅有的解是 y ≡ ±1 (mod p)，因为 (y + 1)(y - 1)必须是 p 的倍数)。注意，如果在该序列中出现了 n – 1，则该序列中的下一个值一定是 1。因为：(n – 1)² ≡ n² – 2n + 1 ≡ 1 (mod n)。在该算法中：

该算法用于判断一个大于 3 的奇数 n 是否素数。参数 k 用于决定 n 是素数的概率。
该算法能够肯定地判断 n 是合数，但是只能说 n 可能是素数。
第 01 行，将 n – 1 分解为 2^s·d 的形式，这里 d 是奇数。
第 02 行，将以下步骤(第 03 到 10 行)循环 k 次。
第 03 行，◇在 [2, n - 2] 的范围中独立和随机地选择一个正整数 a 。
第 04 行，◇计算该序列的第一个值：x ← a^d mod n 。
第 05 行，◇如果该序列的第一个数是 1 或者 n - 1，符合上述条件，n 可能是素数，转到第 03 行进行一下次循环。
第 06 行，◇循环执行第 07 到 09 行，顺序遍历该序列剩下的 s – 1 个值。
第 07 行，◇◇计算该序列的下一个值：x ← x² mod n 。
第 08 行，◇◇如果这个值是 1 ，但是前边的值不是 n - 1，不符合上述条件，因此 n 肯定是合数，算法结束。
第 09 行，◇◇如果这个值是 n - 1，因此下一个值一定是 1，符合上述条件，n 可能是素数，转到第 03 行进行下一次循环。
第 10 行，◇发现该序列不是以 1 结束，不符合上述条件，因此 n 肯定是合数，算法结束。
第 11 行，已经对 k 个独立和随机地选择的 a 值进行了检验，因此判断 n 非常有可能是素数，算法结束。

在一次检验中，该算法出错的可能顶多是四分之一。如果我们独立地和随机地选择 a 进行重复检验，一旦此算法报告 n 是合数，我们就可以确信 n 肯定不是素数。但如果此算法重复检验 25 次报告都报告说 n 可能是素数，则我们可以说 n “几乎肯定是素数”。因为这样一个 25 次的检验过程给出关于它的输入的错误信息的概率小于 (1/4)²⁵。这种机会小于 10¹⁵ 分之一。即使我们以这样一个过程验证了十亿个不同的素数，预料出错的概率仍将小于百万分之一。因此如果真出了错，与其说此算法重复地猜测错，倒不如说由于硬件的失灵或宇宙射线的原因，我们的计算机在它的计算中丢了一位。这样的概率性算法使我们对传统的可靠性标准提出一个问号：我们是否真正需要有素性的严格证明。(以上文字引用自 Donald E. Knuth 所著的《计算机程序设计艺术第2卷半数值算法(第3版)》第 359 页“4.5.4 分解素因子”中的“算法P(概率素性检验)”后面的说明)

SPOJ 288判断2^63-1以内的一个数是否为素数（由于需要大数，所以用python写）

import random

def QuickPow(a, b, MOD):
    ret = 1
    tmp = a%MOD
    while b>0:
        if (b&1):
            ret = (ret*tmp)%MOD
        tmp = (tmp*tmp)%MOD
        b >>= 1
    return ret

def Miller_Rabin(a, p): # a^(p-1) = 1 (mod p) 
    p1 = p-1
    s2 = p1 & -p1 # fetch the last 1
    x = QuickPow(a, p1//s2, p)
    if x == 1 or x == p1:
        return True
    while s2>1:
        x = (x*x)%p
        if x == 1:
            return False
        if x == p1:
            return True
        s2 >>= 1
    return False

def IsPrime(p, k):
    if p == 2 or p == 3:
        return True
    if p < 2 or (p&1) == 0:
        return False
    for i in range(k):
        if not Miller_Rabin(random.randint(2, p-1), p):
            return False
    return True

n = int(input())
for i in range(n):
    p = int(input())
    print('YES' if IsPrime(p, 1) else 'NO')

View Code

现利用C++写了一个Miller-Rabin的模板，不知道为什么上面的在int下只以那3个数为底会有几个错误（内含测试）

用随机数5个进行测试，10^8范围只有1个错误, 不过很奇怪10^9范围没有错误

#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
int x;

inline long long QuickPow(long long a,long long n,long long MOD){
    long long ret=1,tmp=a%MOD;
    while(n){
        if(n&1) ret=ret*tmp%MOD;
        tmp=tmp*tmp%MOD;
        n>>=1;
    }
    return ret;
}

inline bool Miller_Rabin(int x, int a) // a^(x-1) = 1 (mod x)
{
    int tmx=x-1;
    int s2=tmx & -tmx;
    long long res=QuickPow(a, tmx/s2, x);
    if(res == 1 || res == tmx)
        return 1;
    while(s2>1)
    {
        res=(res*res)%x;
        if(res == 1)
            return 0;
        if(res == tmx)
            return 1;
        s2>>=1;
    }
    return 0;
}

inline bool IsPrime(int x, int k)
{
    if(x == 2 || x == 3) return 1;
    if(x < 2 || x%2 == 0 || x%3 == 0) return 0;
    while(k--)
        if(!Miller_Rabin(x, rand()%(x-2)+2))
            return 0;
    return 1;
}

bool pd[10000005];
int main()
{
    srand(time(NULL));
    pd[1]=1;
    int count=0;
    for(int i=1; i<=10000000; i++)
    {
        if(IsPrime(i, 5) == pd[i])
            count++;
        if(!pd[i])
            for(int j=i+i; j<=10000000; j+=i)
                pd[j]=1;
    }
    printf("%d
", count);
    return 0;
}

View Code