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