一.通过素数的基本性质
根据素数的性质(除了1和此整数(n)自身外,无法被其他自然数整除的数):即从2到n/2的数都不能整除n。
isPrime(BigInteger num) 2 { 3BigInteger two = BigInteger.valueOf(2); 4for(BigInteger i = two; !(i.compareTo(num.divide(two)) == 1); i = i.add(BigInteger.ONE)) 5 { 6if(num.remainder(i) == BigInteger.ZERO) 7 { ; 9 } 10 } ; 13 }
用大于2^63的数去测试,结果因为运算量太大,运行半个来小时也没有结果出现。
二.通过素数表
要提高速度就要减少进入判断方法中的循环:
1.偶数可以排除
2.大的合数(即素数的积)可以排除
排除偶数直接增加一个判断即可实现,而排除大的合数也通过产生一个素数表实现。
这里引援51CTO网友 梦朝思夕的BOLG,即“
primeList[1999] = 17389
for(int i = 0, j = 2; i < 2000; j++){if(isPrime(j)){primeList[i] = BigInteger.valueOf(j);i++;}}
再来一个方法判断新生成的大数判断是否为几个素数的积
isNotPrimeProduct(BigInteger num){for(int i=0;i< 2000; i++){if(num.remainder(primeList[i]) == BigInteger.ZERO){return false;}}return true;}
素数表太大也减慢速度,而且数值越大,素数表判别的确定性就越小。要知道,我们要的是2^63。
三.通过费马(Fermat)素数检验
在网上查阅资料,香港空间,知道可以运用费马小定理检验一个数是否不是合数。
费马小定理是数论中的一个定理:假如a是一个整数,p是一个质数,那么
如果a不是p的倍数,这个定理也可以写成
来自wiki
根据费马小定理:如果p是素数,网站空间,,那么
如果我们想知道n是否是素数,我们在中间选取a,美国空间,看看上面等式是否成立。如果对于数值a等式不成立,那么n是合数。如果有很多的a能够使等式成立,那么我们可以说n可能是素数,或者伪素数。
在我们检验过程中,有可能我们选取的a都能让等式成立,然而n却是合数。这时等式
被称为Fermat liar。如果我们选取满足下面等式的a
那么a也就是对于n的合数判定的Fermat witness。
来自wiki
而在这里我从cnblogs的Knuth_档案学到了大量理论知识和算法的实现。(特别是蒙哥马利快速积模算法:计算大数(x^y)%z)
用java实现如下
public static BigInteger Montgomery(BigInteger n, BigInteger p, BigInteger m){n = n.remainder(m) ;BigInteger k = BigInteger.ONE;while(p.compareTo(BigInteger.ONE) == 0){if(!(p.remainder(BigInteger.ONE) == BigInteger.ZERO)){k = (k.multiply(n)).remainder(m);}n = (n.multiply(n)).remainder(m);p = p.divide(BigInteger.valueOf(2));}return (n.multiply(k)).remainder(m);}
接下来,我们就可以对一个大数使用费马素数检验可以判定这个大数是伪素数。
从前2000素数一一检验,而费马素数检验只是随机化了。
fermatPrimalityTest(BigInteger num){for(int i = 0; i < 2000; i++){if(!(Montgomery(primeList[i], num.subtract(BigInteger.ONE), num).compareTo(BigInteger.ONE) == 1)) //(x^y)%z{return false;}}return true;}
使用素数表的前十个结果:
9223372036854775809922337203685477581192233720368547758139223372036854775815922337203685477581792233720368547758199223372036854775821922337203685477582392233720368547758259223372036854775827
使用费马素数检验过的前十个结果:
如果你在以的话,别人就会知道你害怕被说,他们就会加倍地说你,