rsa吧 关注:84贴子:248
  • 1回复贴,共1

关于Miller-Rabin素性测试的误判概率

只看楼主收藏回复

关于Miller-Rabin素性测试。
选定一个底,进行一次测试,误判概率最大为1/4。
即进行k次测试,最小正确率为1-(1/4)^k。
当k取7时,误判概率为0.00006103515625。
但实际上,查到资料,当选取2、3、5、7、11、13、17这7个数时,
所有不超过341 550 071 728 320的数判定结果都正确。
为何实际情况和错误率偏差这么大?


IP属地:广东1楼2015-08-30 18:44回复
    你这个 所有不超过341 550 071 728 320的数 指的是不是小于341550071728320 的数都100%满足米勒定理? 是不是想表达这个意思 然后问 为什么还有那么个概率?


    2楼2016-05-28 16:52
    回复