密码学|概率论 5.3.3 蒙特卡罗算法

密码学 1年前 (2022) admin
402 0 0
5.3.3
蒙特卡罗算法
在实际运用中,有许多算法的输出并不能保证正确。例如。3.4一节描述的Miller–Rabin算法,该算法用于检查给定的大数是否为素数。在实践中,我们多次运行算法以获得 “可能” 正确的输出。在应用这些所谓的蒙特卡洛或概率算法时,重要的是能够计算结果的可信度,即输出正确结果的概率。在本节中,我们将描述如何使用贝叶斯公式进行此类计算。
计算的基础场景由一个大的(可能是无限的)整数集和一个有趣的属性  组成。例如, 可以是所有整数的集合,或者  可能是介于 和  之间的所有整数的集合。属性  可以是复数属性
现在假设我们正在寻找一个不具有属性  的数字。使用 Miller–Rabin 检验,我们可能会寻找 和  之间的非复数整数,即质数。一般来说,假设我们在  中给定一个整数 ,并且我们想知道  是否具有属性 。通常我们大概知道  中有多少整数具有属性 ,例如,我们可能知道99%的元素具有属性  而其他1%的元素没有属性 。然而,比较难确定一个给定的  是否具有属性 。因此,我们选择了一个较快的算法,但它并不一定是正确的。
属性  的蒙特卡罗算法将数  和一个随机数  作为输入(详见Miller–Rabin 检验算法),并根据以下规则返回 Yes 或 No 作为输出:
  1. 如果算法返回 ,那么  必定具有属性 ,记为 

  2. 如果  具有属性 ,那么算法返回  的概率至少为 ,记为 

现在假设我们对整数  运行算法  次,每次都选择一个新的随机数 。如果第一次尝试就返回 ,那么我们知道  具有属性 。但是假设所有  次尝试都返回答案 。有多大的可能  不具有属性 ?记为 
实际上我们希望,当  较大时,这个概率与  接近。由此我们定义两个事件

于是我们考虑条件概率 ,即当算法返回  次  的情况下,整数  不具有属性  的概率,我们可以通过贝叶斯公式(5.21)进行计算

我们根据素数分布设定 
然后我们考虑 ,如果  不具有属性 ,那么根据我们的蒙特卡罗算法性质1(),算法会返回 。从而有 
最后,我们考虑 ,因为运行的  次算法都是相互独立的,于是
把这些值代入贝叶斯公式,我们发现,如果算法返回  次 ,那么  不具备性质  的可能性为

注意到,如果  较大,那么下界就会趋向于 
例如,如果运行 100 次算法均返回 ,那么  不具有性质  的概率至少为

因此,我们基本可以得出结论, 不具有属性 
END


       

原文始发于微信公众号(山石网科安全技术研究院):密码学|概率论 5.3.3 蒙特卡罗算法

版权声明:admin 发表于 2022年12月14日 上午10:45。
转载请注明:密码学|概率论 5.3.3 蒙特卡罗算法 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...