-
-
[讨论]对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哪个速度更快更好,我没有测试过,仅作为对素数测试的一种参考吧,不知道是否正确,望各位批评指正。
能否反过来判断?
对于一个奇数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哪个速度更快更好,我没有测试过,仅作为对素数测试的一种参考吧,不知道是否正确,望各位批评指正。
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!
赞赏
他的文章
- [原创]整数分解随笔(九) 31790
- [原创]整数分解随笔(8) 20178
- [原创]整数分解随笔(7) 18749
- [原创]整数分解随笔(一个算法) 9111
- [原创]整数分解随笔(六) 5975
看原图
赞赏
雪币:
留言: