論文の概要: Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation

• arxiv url: http://arxiv.org/abs/2604.02311v1
• Date: Thu, 02 Apr 2026 17:52:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-03 14:21:10.980639
• Title: Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation
• Title（参考訳）: 資源推定を伴う楕円曲線離散対数に対する空間効率のよい量子アルゴリズム
• Authors: Han Luo, Ziyi Yang, Ziruo Wang, Yuexin Su, Tongyang Li,
• Abstract要約: 楕円曲線離散対数問題(ECDLP)は広く展開されている楕円曲線暗号システムの量子セキュリティを評価する上で重要である。 ECDLPのための空間効率のよいモジュラインバージョンアルゴリズムを提案する。 特に256ビットの素体曲線の場合、これまでのHner et alの低幅実装の2124と比較して、論理キュービット数は1333に減少する。
• 参考スコア（独自算出の注目度）: 30.009533492838028
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimizing the number of logical qubits required to execute this algorithm is a key object. In implementations of Shor's algorithm, the space complexity is largely dictated by the modular inversion operation during point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing method of Proos and Zalka and propose a space-efficient reversible modular inversion algorithm. We use length registers together with location-controlled arithmetic to store the intermediate variables in a compact form throughout the computation. We then optimize the stepwise update rules and give concrete circuit constructions for the resulting controlled arithmetic components. This leads to a modular inversion circuit that uses $3n + 4\lfloor \log_2 n \rfloor + O(1)$ logical qubits and $204n^2\log_2 n + O(n^2)$ Toffoli gates. By inserting this modular inversion component into the controlled affine point-addition circuit, we obtain a space-efficient algorithm for the ECDLP with $5n + 4\lfloor \log_2 n \rfloor + O(1)$ qubits and $O(n^3)$ Toffoli gates. In particular, for a 256-bit prime-field curve, our estimate reduces the logical-qubit count to 1333, compared with 2124 in the previous low-width implementation of Häner et al.
• Abstract（参考訳）: 楕円曲線離散対数問題(ECDLP)の解法は、広く展開された楕円曲線暗号システムの量子セキュリティを評価する上で重要である。 したがって、このアルゴリズムを実行するのに必要な論理量子ビットの数を最小化することが鍵となる。 Shorのアルゴリズムの実装では、空間の複雑さは、点加算時のモジュラー反転演算によって決定される。 拡張ユークリッドアルゴリズム(EEA)から、ProosとZalkaのレジスタ共有法を改良し、空間効率の良い可逆的モジュラー逆アルゴリズムを提案する。 我々は、長さレジスタと位置制御演算を用いて、計算全体を通して中間変数をコンパクトな形式で格納する。 次に、段階的に更新ルールを最適化し、制御された演算部品に対して具体的な回路構成を与える。 これにより、3n + 4\lfloor \log_2 n \rfloor + O(1)$論理量子ビットと204n^2\log_2 n + O(n^2)$トフォリゲートを使用するモジュラー反転回路が生成される。 このモジュラー反転成分を制御されたアフィン点付加回路に挿入することにより, 5n + 4\lfloor \log_2 n \rfloor + O(1)$ qubits および $O(n^3)$ Toffoli gates を用いた ECDLP の空間効率アルゴリズムを得る。 特に256ビットの素体曲線では、Häner et al の以前の低幅実装の 2124 と比較して、この推定は論理キュービット数 1333 に減少する。

関連論文リスト

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。 本手法の様々な応用は, 微分問題を解く文脈で論じる。
  論文  参考訳（メタデータ） (2026-02-11T07:24:33Z)
• Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA [45.810803542748495]
  ウィンドウ演算は、空間時間トレードオフを伴う量子回路のコストを削減する手法である。 この作業では、ウィンドウ化されたモジュラー指数に4つの最適化を導入する。 これにより、暗号化アプリケーションに関連するモジュール型指数回路において、Toffoli数とToffoli深度が3%向上する。
  論文  参考訳（メタデータ） (2025-02-24T16:59:16Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Space-Efficient and Noise-Robust Quantum Factoring [10.974556218898435]
  Regevの最近の量子ファクタリングアルゴリズムに2つの改善がある。 レゲフの回路は$O(n3/2)$ qubitsと$O(n3/2 log n)$ gatesを必要とする。 Regev氏の古典的な後処理手順の分析は、すべての$approx sqrtn$の実行を成功させる必要がある。
  論文  参考訳（メタデータ） (2023-10-02T04:31:21Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。