转自:http://www.cnblogs.com/edwardstudy/archive/2012/11/24/2784174.html
一.通过素数的基本性质
根据素数的性质(除了1和此整数(n)自身外,无法被其他自然数整除的数):即从2到n/2的数都不能整除n。
按 Ctrl+C 复制代码
按 Ctrl+C 复制代码
用大于2^63的数去测试,结果因为运算量太大,运行半个来小时也没有结果出现。
二.通过素数表
要提高速度就要减少进入判断方法中的循环:
1.偶数可以排除
2.大的合数(即素数的积)可以排除
排除偶数直接增加一个判断即可实现,而排除大的合数也通过产生一个素数表实现。
这里引援51CTO网友 梦朝思夕 的BOLG,即“一般来说整除100 以内的所有素数可排除76% 不是素数的可能性 整除256以内的所有素数可排除80% 不是素数的可能性。” 而我同样地建大小为2000的表,private static BigInteger[] primeList = new BigInteger[2000]
primeList[1999] = 17389
for(int i = 0, j = 2; i < 2000; j++)
{
if(isPrime(j))
{
primeList[i] = BigInteger.valueOf(j);
i++;
}
}
再来一个方法判断新生成的大数判断是否为几个素数的积
public static boolean 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是一个质数,那么<iframe id="iframe_0.12259612022899091" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 669px;" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://upload.wikimedia.org/math/9/3/2/932d312464b299b86f5e760c1ad0d1ec.png?_=2784174%22%20style=%22border:none;max-width:669px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.12259612022899091',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" frameborder="0" scrolling="no"></iframe>
如果a不是p的倍数,这个定理也可以写成
<iframe id="iframe_0.5152008500881493" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 669px;" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://upload.wikimedia.org/math/6/5/a/65a9d7295e7bd6db0a8ec7b6cd74ae58.png?_=2784174%22%20style=%22border:none;max-width:669px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.5152008500881493',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" frameborder="0" scrolling="no"></iframe>
|
来自wiki
根据费马小定理:如果p是素数,<iframe id="iframe_0.04923537909053266" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 669px;" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://upload.wikimedia.org/math/2/5/3/253e404f0744634e128dadfacba12b53.png?_=2784174%22%20style=%22border:none;max-width:669px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.04923537909053266',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" frameborder="0" scrolling="no"></iframe>,那么<iframe id="iframe_0.6658551236614585" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 669px;" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://upload.wikimedia.org/math/6/5/a/65a9d7295e7bd6db0a8ec7b6cd74ae58.png?_=2784174%22%20style=%22border:none;max-width:669px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.6658551236614585',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" frameborder="0" scrolling="no"></iframe>
如果我们想知道n是否是素数,我们在中间选取a,看看上面等式是否成立。如果对于数值a等式不成立,那么n是合数。如果有很多的a能够使等式成立,那么我们可以说n 可能是素数,或者伪素数。
在我们检验过程中,有可能我们选取的a都能让等式成立,然而n却是合数。这时等式
<iframe id="iframe_0.24898810521699488" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 669px;" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://upload.wikimedia.org/math/2/e/3/2e3402f60acea95ebfc5ea589fd95c61.png?_=2784174%22%20style=%22border:none;max-width:669px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.24898810521699488',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" frameborder="0" scrolling="no"></iframe>
被称为Fermat liar。如果我们选取满足下面等式的a
<iframe id="iframe_0.25041508045978844" style="margin: 0px; padding: 0px; border-style: none; border-width: initial; width: 669px;" src="data:text/html;charset=utf8,%3Cimg%20id=%22img%22%20src=%22http://upload.wikimedia.org/math/4/f/5/4f5d7dbc502ef72888384995e396d2e2.png?_=2784174%22%20style=%22border:none;max-width:669px%22%3E%3Cscript%3Ewindow.onload%20=%20function%20()%20%7Bvar%20img%20=%20document.getElementById('img');%20window.parent.postMessage(%7BiframeId:'iframe_0.25041508045978844',width:img.width,height:img.height%7D,%20'http://www.cnblogs.com');%7D%3C/script%3E" frameborder="0" scrolling="no"></iframe>
那么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素数一一检验,而费马素数检验只是随机化了。
public static boolean 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;
}
使用素数表的前十个结果:
9223372036854775809
9223372036854775811
9223372036854775813
9223372036854775815
9223372036854775817
9223372036854775819
9223372036854775821
9223372036854775823
9223372036854775825
9223372036854775827
使用费马素数检验过的前十个结果:
9223372036854775817
9223372036854775837
9223372036854775889
9223372036854775903
9223372036854775907
9223372036854775931
9223372036854775937
9223372036854775939
9223372036854775949
9223372036854775963
四.总结
现在我们可以通过结果简单的分析出出只是使用素数表的结果有很多都通不过费马素数检验,因为素数表总有上界。最后可以通过Knuth所说的 拉宾米勒测试排除掉那些卡尔麦克(Carmichael)数。
相关推荐
本人利用网上找的一个C#版的大整数类BigInteger(本人认为这是偶发现的效率最高的一个C#版大整数类)来实现私钥加密公钥加密(事实上也完全支持公租加密私钥解密),但没有使用类BigInteger的大素数生成函数,而是...
使用BigInteger类实现,实现了RSA的加解密
用java写的BigInteger,主要是实现一个内库
JavaScript支持大整数,页面需要进入BigInteger.js。才能使用
用C#编写的大整数类,可生成大素数,用于RSA加密,注释非常详细
大整数 C ++实现BigInteger
BigInteger不是基本数据类型之一,它其实更像String,是Java里的一个类,然而它的初始化方式却没有String那么方便可以直接赋值,而是跟其他自定义的类一样,要调用它的构造器进行初始化。
GarbaGe的东西降价了!!!一分,就一分!!!好东西一定要分享啊啊啊!!! 本模板为高精度模板,大概可存储200位。 目前只支持:输入、输出、赋值、加法。 会不定期更新,请多多资瓷!
BGN是一种同态加密方案,是Boned D等人在2005提出的一种具有全同态性质的加密方案。和传统的仅能支持单同态的elgamal和paillier加密方案...BGN的实现我们主要使用JAVA中的大整数math.BigInteger类以及双线性库JPBC实现
自己根据java的biginteger改写的c++大整数类,除法效率比较低,其他都还没什么问题
java biginteger源码JavaScript ...算法的其余部分,包括解密和密钥生成。 - 基本的熵收集器和 RNG 接口,需要一个 PRNG 后端来定义prng_newstate() 。 - ARC4基于PRNG后端为rng.js ,非常小。 - Base64 编码和解码例
C# 实现的BigInteger操作 简单,快速..
BigInteger, JS插件脚本
C#写的BigInteger,我也是下载的,在这个和大家分享吧
大整数 为Java实现BigInteger
biginteger源码笔记 The Java:trade_mark: Cryptography Architecture requires that Java security providers be code-signed (using a code-signing certificate issued by Oracle Corporation). OpenJDK does not...
JAVABigInteger包.pdf
用java的biginteger实现的poj1001,比较简单的方法
CSharp 4.0 .Net Framework V4.0 BigInteger 结构
类似java里面的BigInteger类型,进行大数存储和计算!