※ 引述《KMLin (小乖)》之銘言：
: ※ 引述《Freak1033.bbs@ptt.cc (金が信念! XD)》之銘言：
: : http://mathworld.wolfram.com/PrimalityTest.html
: : 方法有很多,
: : 甚至有 deterministic 的方法已經能做到 polynomial time.
: : 不過這些方法的原理都不是很容易, 實做上也有一定困難度.
: 目前最實用的是Miller法, 大約 O(\log^2 n)*#iteration, 有夠快, 實做也簡單.
: 它是RP, 每跑一圈至少增加一半信心 (意指: 是質數的可能性趨近一, 但不是一).
: 對deterministic法(AKS)有興趣的, 也可參考 http://fatphil.org/maths/AKS/
我想順便再問個問題,
因為我的數學不太好, 讀這些都有點不求甚解,
我想知道關於這些 probablistic 的方法,
它們是對任何數字多跑幾次, 正確率就會逼近 1,
還是對於某些數字可能有死角?
寫成算式就是,
是
For all sufficiently large n, some polynomial function p,
Pr[A(n)=IsPrime(n)]>=1/p(ln(n))
還是
For uniformly choose at random n={0,1}^l, some polynomial function p,
Pr[A(n)=IsPrime(n)]>=1/p(l)
另外就是它們 false positive 或 false negative 的情形?
Pr[A(n)=True and IsPrime(n)=False]=0
以及
Pr[A(n)=False and IsPrime(n)=True]=0
有哪些演算法會成立這些?
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 140.109.224.64