離散対数問題に対するShorアルゴリズムの実装と量子計算機シミュレータを用いた実験

• Item type: SIG Technical Reports(1)
• 公開日: 2023-07-17
• タイトル: 離散対数問題に対するShorアルゴリズムの実装と量子計算機シミュレータを用いた実験
• タイトル / 言語: en
• タイトル: Implementation of Shor’s algorithm for the discrete logarithm problem and experiments using the quantum computer simulator
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ISEC
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 富士通株式会社富士通研究所
• 著者所属: 富士通株式会社富士通研究所
• 著者所属: 富士通株式会社富士通研究所
• 著者所属: 筑波大学システム情報系
• 著者所属(英): en
• 著者所属(英): Fujitsu Research, Fujitsu
• 著者所属(英): en
• 著者所属(英): Fujitsu Research, Fujitsu
• 著者所属(英): en
• 著者所属(英): Fujitsu Research, Fujitsu
• 著者所属(英): en
• 著者所属(英): Institute of Systems and Information Engineering, University of Tsukuba
• 著者名: 岸, 海斗; 山口, 純平; 伊豆, 哲也; 國廣, 昇
• 著者名(英): Kaito, Kishi; Junpei, Yamaguchi; Tetsuya, Izu; Noboru, Kunihiro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 暗号分野でよく用いられる素体上の離散対数問題は古典計算機では解くための多項式時間アルゴリズムが見つかっていない．一方，量子計算機による多項式時間アルゴリズムが Shor により与えられており，離散対数問題を解くのに必要なゲート数などのリソースを見積もることが求められている．しかし，素因数分解と比べて離散対数問題を解く量子シミュレーション結果は不足しており，その見積もりをするには不十分である．本研究では 32 量子ビットで可能な 1860 通りすべての離散対数問題を解く量子シミュレーションを行い，加算に Q-ADD を用いると標数が 2048 ビットのときは 8194 量子ビットと 1.04 ˆ 1015 の量子ゲートが必要と推定できた．また，量子計算機が解くにあたって他のパターンと比べて難しいような離散対数問題の種類を発見した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Classical polynomial-time algorithms for solving the discrete logarithm problem (DLP) over a prime field have not been found yet, and many cryptosystems are constructed based on them. However, a quantum polynomial-time algorithm for it was given by Shor. Previous quantum simulates to estimate resources for solving DLP are still lacking. In this study, we estimated that 8194 qubits and 1.04 ˆ 1015 quantum gates are required to solve DLP of a 2048 bits characteristic with Q-ADD by simulating quantum circuits solving 1860 patterns of DLP. We also found a type of DLP which are more difficult than other types of them to solve in quantum computers.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11235941
• 書誌情報: 研究報告コンピュータセキュリティ（CSEC）; 巻 2023-CSEC-102, 号 39, p. 1-8, 発行日 2023-07-17
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8655
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会