首页
社区
课程
招聘
[讨论]对miller-rabin反向取数的测试
发表于: 2014-2-2 09:38 3547

[讨论]对miller-rabin反向取数的测试

2014-2-2 09:38
3547
对于miller-rabin 的判断是把1个奇数写成d×2^n,其中d为奇数, 进行费马测试 a^d mod p,为1,不为1,再进行二次探测,根据a^n a^(2n) a^(4n)…a^(p-1) mod p看是否为-1,如果为-1,则可能为素数,否则肯定是合数。
能否反过来判断?
对于一个奇数n,a^((n-1)/2) mod n,看是否为为-1,如果为-1,可能是素数,否则肯定不是素数,如果为1,则判断(n-1)/2是否为奇数,如果为奇数,可能是素数,不为1,肯定不是素数,算法如下(n为奇数):
1 i=(n-1)/2
2 m= a^i mod n
3 if  m =-1  n可能是素数 exit
if   m=1  且 i为奇数  n可能是素数 exit
  if m<> -1 or m<>1 n肯定不是素数 exit
4 i=i//2   重复 1

对于miller_rabin测试方法,  9可以通过测试,用上述测试方法,9不会通过测试,但在10000内以2为底共有5个合数通过测试:2047  3277  4033  4681  8321(详见附录)。
不过这个的算法与miller-rabin哪个速度更快更好,我没有测试过,仅作为对素数测试的一种参考吧,不知道是否正确,望各位批评指正。

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

上传的附件:
收藏
免费 0
支持
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回
//