机构名称：
¥ 4.0
摘要本文重点研究了在 Z ∗ N 中因式分解和计算离散对数的量子算法中逻辑量子比特数量的优化。这些算法包含一个模 N 幂运算电路，它占了大部分成本，包括量子比特和运算成本。在本文中，我们表明，仅使用 o (log N ) 个工作量子比特，就可以获得模幂运算输出的最低有效位。我们将此结果与 May 和 Schlieper 的截断技术 (ToSC 2022) 以及 Shor 算法的 Eker˚aH˚astad 变体 (PQCrypto 2017) 相结合，仅使用 d + o (log N ) 个量子比特来解决 Z ∗ N 中的离散对数问题，其中 d 是对数的比特大小。因此，我们可以使用 n/2 + o(n) 个量子位来因式分解 n 位 RSA 模数，而当前设想的实现需要大约 2n 个量子位。我们的算法使用余数系统，并且以可参数化的概率成功。由于它是完全经典的，我们已经实现并测试了它。对于 RSA 因式分解，我们可以达到深度 O(n2log3n) 的门数 O(n3)，然后必须将其乘以 O(logn)（Eker˚aH˚astad 所需的测量结果数）。要因式分解一个 RSA-2048 实例，我们估计 1730 个逻辑量子位和 236 个 Toffili 门就足以进行一次运行，而该算法平均需要 40 次运行。为了解决 2048 位安全素数组中 224 位（112 位经典安全性）的离散对数实例，我们估计 684 个逻辑量子位就足够了，并且每次使用 2 32 Toffili 门进行 20 次运行。
减少量子因式分解中的量子比特数量
主要关键词
相关文件推荐
