#密码学 47 个 #概率论 3 个 5.3.3 蒙特卡罗算法 在实际运用中，有许多算法的输出并不能保证正确。例如。3.4一节描述的Miller–Rabin算法，该算法用于检查给定的大数是否为素数。在实践中，我们多次运行算法以获得 “可能” 正确的输出。在应用这些所谓的蒙特卡洛或概率算法时，重要的是能够计算结果的可信度，即输出正确结果的概率。在本节中，我们将描述如何使用贝叶斯公式进行此类计算。 计算的基础场景由一个大的（可能是无限的）整数集和一个有趣的属性 组成。例如， 可以是所有整数的集合，或者 可能是介于 和 之间的所有整数的集合。属性 可以是复数属性 现在假设我们正在寻找一个不具有属性 的数字。使用 Miller–Rabin 检验，我们可能会寻找 和 之间的非复数整数，即质数。一般来说，假设我们在 中给定一个整数 ，并且我们想知道 是否具有属性 。通常我们大概知道 中有多少整数具有属性 ，例如，我们可能知道99%的元素具有属性 而其他1%的元素没有属性 。然而，比较难确定一个给定的 是否具有属性 。因此，我们选择了一个较快的算法，但它并不一定是正确的。 属性 的蒙特卡罗算法将数 和一个随机数 作为输入（详见Miller–Rabin 检验算法），并根据以下规则返回 Yes 或 No 作为输出： 现在假设我们对整数 运行算法 次，每次都选择一个新的随机数 。如果第一次尝试就返回 ，那么我们知道 具有属性 。但是假设所有 次尝试都返回答案 。有多大的可能 不具有属性 ？记为 实际上我们希望，当 较大时，这个概率与 接近。由此我们定义两个事件 于是我们考虑条件概率 ，即当算法返回 次 的情况下，整数 不具有属性 的概率，我们可以通过贝叶斯公式（5.21）进行计算 我们根据素数分布设定 然后我们考虑 ，如果 不具有属性 ，那么根据我们的蒙特卡罗算法性质1（），算法会返回 。从而有 最后，我们考虑 ，因为运行的 次算法都是相互独立的，于是 把这些值代入贝叶斯公式，我们发现，如果算法返回 次 ，那么 不具备性质 的可能性为 注意到，如果 较大，那么下界就会趋向于 。 例如，如果运行 100 次算法均返回 ，那么 不具有性质 的概率至少为 因此，我们基本可以得出结论， 不具有属性 END
周飒博客-ZhouSa.com 如果算法返回 ，那么 必定具有属性 ，记为
如果 具有属性 ，那么算法返回 的概率至少为 ，记为
还没有评论，来说两句吧...