Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA

Luongo, Narasimhachar, Sireesh · 2025 · arXiv 预印本

| 编号 QEXP019 | 主题 模幂与 Shor | 链接 arXiv:2502.17325 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

Windowed arithmetic [Gidney, 2019] is a technique for reducing the cost of quantum arithmetic circuits with space—time tradeoffs using memory queries to precomputed tables. It can reduce the asymptotic cost of modular exponentiation from $O\left(n^3\right)$ to $O\left(n^3/{\log }^{2}n\right)$ operations, resulting in the current state-of-the-art compilations of quantum attacks against modern cryptography. In this work we introduce four optimizations to windowed modular exponentiation. We (1) show how the cost of unlookups can be reduced by $66\%$ asymptotically in the number of bits, (2) illustrate how certain addresses can be bypassed, reducing both circuit depth and the overall lookup cost, (3) demonstrate that multiple lookup—addition operations can be merged into a single, larger lookup at the start of the modular exponentiation circuit, and (4) reduce the depth of the unary conversion for unlookups. On a logical level, this leads to a $3\%$ improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications. This translates to some improvements on [Gidney and Ekerå, 2021]‘s factoring algorithm: for a given number of physical qubits, our improvements show a reduction in the expected runtime from $2\%$ to $6\%$ for factoring $\mathsf{RSA}$-$2048$ integers.

本站词条在引用该文献时，会以 wikilink（sources/QEXP019）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。