问题
如题
思路
首先太暴力的就不谈,会折寿,有一个强伪证的算法(strong liar)Miller Rabin Test,思路是这样(以下p代表某一个大于2的素数),找到判断素数的必要条件,将多个条件组合起来就能得到近似充分的判断素数条件
两个引理说一下,首先是二次探测定理:如果x2≡1(mod p),那么x≡±1(mod p),或者说不存在模p等于1下的非平凡平方根(证明:p只有1和p两个因子的情况下,(x+1)(x-1)≡0(mod p)只可能有x-1=0或x+1=p)
然后是费马小定理,a和p互质(gcd(a,p)=1)时,ap-1≡1(mod p)
好了开始,对于要判断的数P,任取2-p内的数a,这里我们方便起见取a=2
根据上述条件,p-1一定是偶数,可以分解成2r*d的形式,所以对于a2^r*d ≡1(mod p),也就是(a2^(r-1)*d )2≡1(mod p),设x(n) = (a(2^n*d)) mod p,那么目前的情况是,我们仅有平凡平方根x(r-1)≡±1(mod p)
这里如果x(r-1)≡1(mod p),问题就变得可递归了,因为接下来的方程是a2^(r-1)*d≡1(mod p),然后我们可以继续往下解xn-1,xn-2...
如果是x(r-1)≡-1(mod p),那么问题就更简单了,因为接下来的解不确定,不用往下推了
所以从上往下推我们可以看到,对于函数x的序列,x(r)=1是一定的,而且如果x(t)=-1,那么x(t+1)到x(r)一定都是1,也就是说,对于序列中的数只要判断两个条件即可:
1.1之前的数一定是1或-1
2.最后一个数一定是1
解决
public boolean sPrime_RobinMiller(long p) {
long[] ar = new long[]{2, 3, 5, 7, 11};//if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11.
if (p < 4) return p > 1;
if (p == 5 || p == 7 || p == 11) return true;//a<p-1
for (long a : ar) {
long p1 = p - 1, u = p1 & -p1, d = p1 / u, cur = quickPow(a, d, p), prev = cur;
while (u > 0) {
cur = prev * prev % p;
if (cur == 1 && prev != 1 && prev != p1)
return false;//序列中,1之前的数一定是1或者-1
prev = cur;
u >>= 1;
}
if (cur != 1)
return false;//序列的最后一个数一定是1
}
return true;//all passed
}
private long quickPow(long a, long b, long c) {
long res = 1;
for (; b > 0; b >>= 1, a = a*a%c)
if ((b & 1) == 1) {
res = res * a % c;
}
return res;
}
Tips
- 取a=2,3,5,7,11,对于int范围内所有数(小于2147483648的所有数)都可以判断出结果,注意这时需要对3,5,7,11单独判断一遍,因为前提条件是gcd(a,p)=1
- 并不是所有数据类型取long就能判断出长整型范围内的数据了,因为快速幂中需要计算2d mod p,其中a*a是有可能溢出的
Ref
https://oi-wiki.org/math/prime/
https://zh.wikipedia.org/wiki/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E6%A3%80%E9%AA%8C
网友评论