wsc810 发表于 2012-11-16 11:21:01

是否Carmichael数都不能通过Miller-Rabin检验

是这样吗？？？

qianyb 发表于 2012-11-16 12:06:00

对的

郭先抢 发表于 2012-11-17 12:59:47

楼上回答有问题呀！
对于某一个Carmichael数，有的miller测试能通过，有的不能通过的！

qianyb 发表于 2012-11-20 12:27:43

能通过所有miller测试的数叫Carmichael数

wsc810 发表于 2012-11-20 13:20:47

楼上回答有问题呀！
对于某一个Carmichael数，有的miller测试能通过，有的不能通过的！
郭先抢 发表于 2012-11-17 12:59 http://bbs.emath.ac.cn/images/common/back.gif

能举个例子么？，对能通过miller测试的Carmichael数

mathe 发表于 2012-11-20 19:19:53

Miller测试相对比较弱，但是Miller-Rabin测试挺强的，印象中假设黎曼猜想成立，可以推导出对于任意奇合数n, 前$ln^3(n)$个数中必然存在一个a使得n对关于a为底的Miller-Rabin测试不通过

mathe 发表于 2012-11-20 19:28:26

看了
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test
原来只要$2ln^2(n)$次测试

郭先抢 发表于 2012-11-20 19:30:08

4# qianyb


能够通过所有的fermat测试的才叫Carmichael数.

郭先抢 发表于 2012-11-20 19:31:28

7# mathe


BPSW算法,然后再加上几次miller rabin测试就可以了,足可以采信
页: [1]
查看完整版本: 是否Carmichael数都不能通过Miller-Rabin检验