今天第一次写出miller-rabbin素数测试,知道这个概率算法对于大整数测试是否是素数十分有效,成功率有保证~于是突然想到有没有手机号是素数!
电脑开了半个小时,用miller-rabbin测试,CPU一直保持占用率100%,结果搜结束之后我的data.out里面还是什么都没有!
拿出纸笔,开始计算:如果手机号只有如下几个限制:1、以1开头;2、共11位。根据素数定理,手机号是素数的概率为0.04(以1开头的11位整数大约有4亿个是素数)。
很明显,miller-rabbin出错了!用5000-10000之间的素数对拍了一下,算法没有出错。毫无疑问,快速幂取模时溢出了!
换用O(n^0.5)的素数判断,很快找到了许多素数手机号,列出几个好的手机号吧:
15956880001;
15956880007;
15256880101;
15256888811;
15256885577
还有很多……
posted on 2010-02-20 23:26
lee1r 阅读(483)
评论(0) 编辑 收藏 引用 所属分类:
Programming Diary