※ 引述《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