机构名称：
¥ 1.0
背景。Shor 的突破性算法 [13] 表明，因式分解和计算离散对数的问题可以在量子计算机上在多项式时间内解决。从那时起，许多作者引入了该算法的变体并改进了其成本估算，以尽量减少对量子比特、门数或电路深度的要求 [2、15、14、8、5、12]。由于 Shor 算法被认为是量子计算机与密码分析最相关的应用，这些工作也旨在确定量子计算架构可能变得“与密码相关”的点。在本文中，我们专注于空间优化。考虑群 Z ∗ N 中的离散对数 (DL) 问题，其中 N 为素数。让我们记 n = log 2 N。我们取乘法生成器 G。A 的 DL 是数量 D，使得 A = GD mod N。它是通过对在 Z 2 上定义的函数 f ( x, y ) = G x A − y mod N 调用 Shor 的量子周期查找子程序来找到的。这个子程序只是在所有 ( x, y ) ∈ [0; 2 m 1 − 1] × [0; 2 m 2 − 1] 上调用叠加的 f，执行 QFT 和测量（图 1）。经过一些有效的后处理后，可以找到周期 ( D, 1 )。因此，逻辑量子比特的数量取决于两个参数：输入大小 m 1 + m 2 和工作区大小。对 RSA 半素数 N 进行因式分解可以简化为求解 Z ∗ N 中的 DL 实例，其中 DL 的预期大小为 1
减少量子因式分解中的量子比特数量
主要关键词
相关文件推荐
