看板ACMCLUB
标 题Re: 问题
发信站批踢踢兔 (Sun May 29 11:46:36 2005)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ 引述《KMLin (小乖)》之铭言：
: ※ 引述《[email protected] (金が信念! 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