看板ACMCLUB
标 题Re: 问题
发信站批踢踢兔 (Sun May 29 12:47:19 2005)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ 引述《Freak1033 (I ain't gonna be ever17)》之铭言：
: ※ 引述《KMLin (小乖)》之铭言：
: : 目前最实用的是Miller法, 大约 O(\log^2 n)*#iteration, 有够快, 实做也简单.
: : 它是RP, 每跑一圈至少增加一半信心 (意指: 是质数的可能性趋近一, 但不是一).
: : 对deterministic法(AKS)有兴趣的, 也可参考 http://fatphil.org/maths/AKS/
: 我想顺便再问个问题,
: 因为我的数学不太好, 读这些都有点不求甚解,
: 我想知道关於这些 probablistic 的方法,
: 它们是对任何数字多跑几次, 正确率就会逼近 1,
: 还是对於某些数字可能有死角?
Fermat Test 会有死角 Carmicheal Number，
Miller-Rabin 不会有死角而且 witness 够多 (非 witeness 的机率最多只有 1/4)
--
E PUR SI MUOVE
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.31.131