格子と最適化手法を用いた素因数分解法の実験報告

• Item type: SIG Technical Reports(1)
• 公開日: 2023-05-04
• タイトル: 格子と最適化手法を用いた素因数分解法の実験報告
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: CSEC
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 富士通株式会社
• 著者所属: 富士通株式会社
• 著者所属: 筑波大学システム情報系
• 著者名: 山口, 純平; 伊豆, 哲也; 國廣, 昇
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 2022 年 12 月に Yan らによって Shor アルゴリズムよりも少ない量子ビット (mビット合成数に対して O (m/log m) 量子ビット) で素因数分解可能とする新しい量子アルゴリズムが提案された．これは，平方差法を利用した素因数分解法であり，特に平方差法のうちの関係式収集を格子上の最近ベクトル問題の近似解計算問題に帰着し，古典的なアルゴリズムである LLL や Babai アルゴリズム，量子最適化アルゴリズムである QAOA を用いて近似解を計算するという方法である．本稿では，Yan らの方法では関係式を 1 個から 3 個程度しか計算できないという問題点を指摘し，Yan らの方法を繰り返し実行して素因数分解に成功する十分な数の関係式を計算するアルゴリズムを提案した．また，QAOA の代わりに古典的なアニーリング計算を使用した実験を行い，m = 11 から 55 の各ビットの合成数の素因数分解に成功した．この結果から，素因数分解に成功する十分な数の関係式を収集するには Yan らの主張である O (m/log m) よりも多くの量子ビットを必要とするという見積もりを得た．ただし我々のアルゴリズムは多くのパラメータに依存するため，今後もより詳細な解析が必要である．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12326962
• 書誌情報: 研究報告インターネットと運用技術（IOT）; 巻 2023-IOT-61, 号 22, p. 1-8, 発行日 2023-05-04
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8787
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会