大西洋城算法

2020-07-30 03:31:15

跳转到导航跳转以搜索大西洋城算法是一种概率多项式时间算法,至少有75%的时间是正确回答的(或者,在某些版本中,其他值大于50%)。大西洋城这个术语最早是在1982年由J.Finn在一篇题为“质数的概率检验比较”的未发表手稿中提出的。[1]。

另外两类常见的概率算法是蒙特卡罗算法和拉斯维加斯算法。蒙特卡罗算法总是快速的,但只有可能是正确的。另一方面,拉斯维加斯的算法总是正确的,但可能只是速度快。大西洋城算法是有界概率多项式时间算法,可能是正确的,也可能是快速的。[2]。

理查德·A·莫林(2003)。RSA和公钥加密。Chapman&Amp;Hall/CRC。第80页。

威廉·J·特纳(2002年5月)。带Linbox库的黑盒线性代数。北卡罗来纳州立大学。第3页。