CTF导航 CTF导航

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

密码学 2年前 (2022) admin
422 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导航

相关文章

G.O.S.S.I.P 阅读推荐 2022-12-07 Find-the-Bad-Apples
admin
532
密码学系列｜ 2.7 A Collision Algorithm for the DLP
admin
914
论文分享｜通过更快的安全比较算法和离线阶段实现高效隐私集合求交协议
admin
406
密码学 ｜ 第4章 4.3 Elgamal 数字签名与DSA
admin
670
密码学 ｜ 5.3.5 期望
admin
512
密码学 | 3.10 概率加密与Goldwasser–Micali 密码系统
admin
856

暂无评论

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

相关文章

Netflix Interleaving AB实验个性化推荐算法分析
0
密码学算法概览
0
​一篇关于密码学的概念性文章(上)
0
【RAG提升技巧】查询改写HyDE
0
【RAG入门必备技能】Faiss框架使用与FaissRetriever实现
0
A quick post on Chen’s algorithm
0
A quick post on Chen’s algorithm
0
RSA相关的趣味数学题(7)
0
DKG 协议的门限提升漏洞分析
0
G.O.S.S.I.P 阅读推荐 2024-02-19 密码学误用检测工具的误用？
0