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,偶数也可以全部拉出来特判一次,是偶数就直接返回结果,可以省掉一些询问的时间。
如果还没懂就看代码吧:
首先有两个引理:
1.费马小定理
2.二次探测
这两个引理对于素数均成立,而对于非素数则不一定成立,因此我们就根据这两个性质来排数掉非素数。显然这种方法有一定的错误机率,但是实测错误的机率非常低
算法流程:
首先运用费马小定理:若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;
}
评论
发表评论