量子计算机如何破解加密 | Shor算法解释

How Quantum Computers Break Encryption | Shor's Algorithm Explained

频道:minutephysics · 时长:17:30 · 发布:2019-05-01 · 播放:3357229

在 YouTube 观看

简介

MinutePhysics解释了Shor算法,展示了量子计算机如何通过寻找一个数模N的周期来分解大整数。它讲解了模运算和数论,这些使得量子计算机在分解因数方面比经典计算机有指数级加速,以及为什么这威胁到加密。

HN 为什么推荐

HN评论者指出它是对Shor算法以及量子计算机实际功能的清晰、易懂的解释。

Minute Physics对Shor算法以及由此引申的量子计算有非常好的解释。 — HN, 2019

密码学 · 量子计算

中文字幕节选

加密的目标是把数据弄乱, 使得任何拥有数据的人 都无法读取,除非他们是预期的接收者。 而几乎所有通过互联网发送的私人信息的加密 都极大地依赖于一个数值现象—— 据我们所知,用普通的非量子计算机 对一个非常大的数进行因数分解真的非常非常困难。 与乘法不同,乘法非常快(只需将数字相乘并相加), 而找出相乘得到任意大的非质数的质数 似乎很慢—— 至少,我们目前拥有的最佳方法 在普通计算机上运行——即使是非常强大的计算机——也非常慢。 比如,要找出这个数的因数, 需要2000年的计算机处理器时间! 现在,还没有证明我们最终不会找到一种快速破解加密的方法, 仅仅使用普通计算机,但可以肯定的是 任何拥有大型工作量子计算机的人 今天就会对整个互联网构成直接的隐私 和安全威胁。 这是由于所谓的“Shor算法”。 嗯,实际上是由于量子叠加 和干涉;它们只是被 Peter Shor开发的一种算法所利用, 我现在将尝试解释这个算法。 我们谈论的这种加密使用一个大数来弄乱或“锁定”消息, 使得解密或“解锁” 数据需要知道那个数的因数。 如果某人没有这些因数, 要么他们无法解密数据,要么他们 必须花费非常非常长的时间或 巨大的计算资源投资来找到因数。 我们目前最好的方法基本上只是猜测一个可能是因数的数, 并检查它是否是。如果不是,你再试一次。 再试一次。再试一次。这很慢。 有太多数字需要检查,即使 是快速聪明的做出很好猜测的方法也很慢。 例如,我的电脑花了将近9分钟 才找到这个数的质因数。 所以如果你用这个数来加密你的数据,它只能在我面前安全9分钟。 另一方面,如果你使用一个像 需要2000年计算机处理器时间才能分解的数, 你的数据肯定 对我和我的笔记本电脑是安全的,但对 能够访问服务器农场的人来说就不安全了。这类似于在你的 门上装锁、窗户上装栏杆并不能保证 你的房子不会被偷东西, 但确实需要更多时间和更多工作。 加密数据并不是保护的保证 ——它是一种使其更难访问的方式; 希望足够难,以至于没有人认为值得尝试。 但量子计算有可能 使访问加密数据变得超级超级容易 ——就像拥有一把光剑,你可以用它 砍穿任何锁或屏障,无论多么坚固。 Shor算法就是那把光剑。 粗略地说,为了分解一个给定的数, Shor算法从一个随机的糟糕猜测开始, 这个猜测可能与你的目标数共享一个因数, (但可能没有), 然后算法将其转换为一个 一个很可能确实共享因子的更好的猜测! 这本身并没有任何量子力学的东西—— 事实上,你可以在普通计算机上运行一个版本的 Shor 算法来分解大数, 但也许并不意外的是, 把“糟糕的猜测变成更好的猜测”这一步在普通计算机上要花非常 非常长的时间。 另一方面,这个关键步骤在量子计算机上 却快得离谱。 所以,我们的任务是解释 Shor 算法如何 把一个糟糕的猜测变成更好的猜测(这 纯粹是数学),以及为什么量子计算机

HN 上的讨论

这个视频澄清了大家对 QC 最重要的误解,即“QC 如何并行执行操作,以及当你现实中只能得到一个输出时,这到底意味着什么?”我希望我自己理解正确了,如果正确的话。另外 Minute Physics 关于 Shor 算法的视频也是很好的解释 [VIDEO] — diginova, 2023-04
这对我帮助很大,我想它之前也在 hackernews 上流传过。[LINK] 还有这个视频,它演示了量子计算机如何以经典计算机无法做到的方式解决一个非常特定的因子分解问题(Shor 算法)。[VIDEO] — xmprt, 2021-06
Minute Physics 对 Shor 算法以及由此引申的量子计算有非常好的解释。[VIDEO] 以及后续:[LINK] — glandium, 2019-10

相关视频