机构名称：
¥ 1.0
摘要：得益于最近硬件的进步，量子计算是一个快速发展的研究领域。量子计算机的量子力学特性使它们能够比传统计算机更快地解决某些问题。其中一个问题是非结构化搜索问题，使用众所周知的 Grover 算法，量子机可以比目前可用的最佳效率经典算法（即线性搜索）更高效地解决该问题。量子 p 计算为此类问题提供了二次加速，O(N)，而传统算法提供的线性效率为 O(N)，其中 N 是搜索空间。另一个非常重要的应用是多项式时间量子算法，称为 Shor 算法，用于分解整数和计算离散对数。Shors 算法是第一个实现比传统算法指数加速的量子算法，应用于量子力学领域以外的问题，具有明显的应用价值。具体来说，Shors 算法可用于破解基于对两个大小相似的素数乘积进行因式分解的难度的 RSA 密码体制，以及基于离散对数问题 (DLP) 的密码体制，例如 Diffie-Hellman 密钥协商协议和数字签名算法。Shors 因式分解算法执行的最昂贵的操作是模幂运算。现代经典计算机可以在一秒内对数千位数字执行模幂运算。这两个事实乍一看似乎表明使用 Shors 算法对一千位数进行因式分解只需要几秒钟，但不幸的是（或许幸运的是），事实并非如此。Shors 算法中的模幂运算是在指数叠加上执行的，这意味着需要量子计算机，而量子硬件的噪声预计会比经典硬件高出几个数量级。这种噪声需要使用纠错，这会带来开销，最终使得在量子计算机上执行可靠算术的成本比在传统计算机上高出几个数量级。尽管 Shors 算法在多项式时间内运行，但渐近符号隐藏的常数因子相当大。必须通过各个层面的大量优化来克服这些常数因子，才能使算法实用。目前的量子计算机还远远不能执行与密码相关的问题规模的 Shors 算法。本文提出了一种实现 Shors 量子因式分解算法的方法和实验。实现是使用 Python 和量子计算机模拟完成的
使用 shor 量子计算破解 rsa 加密
主要关键词
相关文件推荐
