Miller Rabin

Miller Rabin是一种快速判定素数的方法,可以在log的时间内判断一个数是否为素数。

首先有两个引理:

1.费马小定理

2.二次探测

这两个引理对于素数均成立,而对于非素数则不一定成立,因此我们就根据这两个性质来排数掉非素数。显然这种方法有一定的错误机率,但是实测错误的机率非常低(脸黑不适合学信竞)。一般来说,我们取40以下的质数就行了。

算法流程:

首先运用费马小定理:若p为质数,a^p-1≡1(mod p),这里的a就是我们上面说的要取的质数,同时根据二次探测定理,若p为质数,a^2≡1(mod p),那么a≡1或n-1(mod p),同时显然若a≡1(mod p),那么a^2≡1(mod p),这样算法的轮廓就逐渐出来了。

首先将p-1一直除以2,我们设得到的结果为t,算出a^t为k,对于k每次进行平方,若平方之后≡1(mod p),那么如果之前mod p的余数不为1或n-1就返回false,同时当k一直乘到p-1之后mod p的余数仍然不为1的话,也返回false。这样当我们多取几个a(一般是40一下素数)判断一下,如果没有返回过false就返回true了。

最后,记得特判1,偶数也可以全部拉出来特判一次,是偶数就直接返回结果,可以省掉一些询问的时间。

如果还没懂就看代码吧:

long long c[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
inline bool Miller_Rabin(long long n)
{
    if (n == 1)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    long long p = n - 1;
    int k = 0;
    while (p % 2 == 0)
    {
        p /= 2;
        k++;
    }
    for (int i = 0; i < 12; ++i)
    {
        if (n == c[i])
            return true;
        long long num;
        num = ksm(c[i], p, n);
        if (num == 1)
            continue;
        for (int j = 1; j <= k; ++j)
        {
            long long nxt = qmul(num, num, n);
            if (nxt == 1 && num != 1 && num != n - 1)
                return false;
            num = nxt;
            if (num == 1)
                break;
        }
        if (num != 1)
            return false;
    }
    return true;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注