整数因数分解
コンピュータサイエンスにおける未解決問題
整数因数分解は古典的コンピュータで多項式時間で解くことができますか?
コンピュータサイエンスにおけるさらなる未解決問題

数学において、整数の因数分解とは、正の整数を整数の積に分解することです。1 より大きいすべての正の整数は、2 つ以上の 1 より大きい整数因数の積である場合は合成数、そうでない場合は素数です。たとえば、15は15 = 3 · 5なので合成数ですが、7 はこのように分解できないので素数です。因数の 1 つが合成数である場合、それはさらに小さな因数の積として表すことができます。たとえば、60 = 3 · 20 = 3 · (5 · 4)です。すべての因数が素数になるまでこの処理を続けることを素因数分解と呼びます。素因数分解定理により、結果は常に因数の順序まで一意になります。

小さな整数n を暗算または紙とペンを使って因数分解する最も簡単な方法は、試し割りです。つまり、 nの平方根まで、2、3、5といった素数で割り切れるかどうかを確認します。より大きな数の場合、特にコンピュータを使用する場合は、より高度な因数分解アルゴリズムの方が効率的です。素因数分解アルゴリズムでは通常、因数が見つかるたびに、 その因数が素数かどうかを判定します。

数が十分に大きい場合、効率的な非量子因数分解アルゴリズムは知られていない。しかし、そのようなアルゴリズムが存在しないことが証明されたわけではない。この問題の想定される困難さは、 RSA公開鍵暗号やRSAデジタル署名などの暗号技術で使用されるアルゴリズムにとって重要である。[ 1 ]楕円曲線、代数的数論、量子コンピューティング など、数学とコンピュータサイエンスの多くの分野がこの問題に取り組んできた。

与えられた長さの数が全て、因数分解するのが等しく難しいわけではありません。これらの問題の中で最も難しい例（現在知られている手法では）は、2つの素数の積である半素数です。2つの素数が両方とも大きく、例えば2000ビット以上の長さで、ランダムに選択され、ほぼ同じサイズ（ただし、フェルマーの因数分解法による効率的な因数分解を回避できないほど近すぎない）の場合、最高速の古典的コンピュータ上で最高速の素因数分解アルゴリズムを用いても、探索が非現実的になるほどの時間がかかります。つまり、因数分解する整数の桁数が増加するにつれて、古典的コンピュータ上で因数分解を実行するために必要な演算数は劇的に増加するのです。

多くの暗号プロトコルは、大きな合成整数の因数分解の困難さ、あるいはそれに関連する問題（例えばRSA問題）に基づいています。任意の整数を効率的に因数分解するアルゴリズムは、RSAベースの公開鍵暗号を安全でないものにしてしまうでしょう。

素分解

n = 864の素分解は2 5 × 3 3

算術の基本定理によれば、すべての正の整数は一意に素因数分解されます。（慣例により、1は空積です。）整数が素因数分解されるかどうかの判定は、例えばAKS素数判定法を用いることで、多項式時間で行うことができます。しかし、合成数の場合、多項式時間判定では因数を求める方法についての知見が得られません。

整数因数分解の一般的なアルゴリズムが与えられれば、このアルゴリズムを繰り返し適用することで、任意の整数をその構成する素因数に分解できます。特殊な目的の因数分解アルゴリズムでは状況はより複雑になり、分解時に生成される因数ではその利点が十分に発揮されない場合や、全く発揮されない場合もあります。例えば、n = 171 × p × q （ p < qが非常に大きな素数）の場合、試し割りによって因数 3 と 19 はすぐに得られますが、次の因数を見つけるにはp回の割り算が必要になります。対照的な例として、n が素数13729、1372933、および18848997161の積である場合( 13729 × 1372933 = 18848997157 ) 、フェルマーの因数分解法は⌈ √ n ⌉ = 18848997159から始まり、すぐにb = √ a 2 − n = √ 4 = 2となり、因数a − b = 18848997157およびa + b = 18848997161となります。これらはそれぞれ合成数と素数として簡単に認識できますが、フェルマー法では、 aの⌈ √ 18848997157 ⌉ = 137292の開始値が1372933の 10 倍であるため、合成数を因数分解するのにはるかに長い時間がかかります。

現在の最先端技術

bビットの数値の中で、既存のアルゴリズムを用いて因数分解するのが最も難しいのは、因数の大きさがほぼ同じである半素数です。そのため、暗号アプリケーションではこれらの整数が用いられます。

2019年、ポール・ツィンマーマン氏を含む研究者チームは、約900コア年の計算能力を用いて、 240桁（795ビット）の数字（ RSA-240 ）を因数分解しました。 [ 2 ]研究者らは、1024ビットのRSA法には約500倍の時間がかかると推定しました。[ 3 ]

これまでに因数分解された最大の半素数は、2020年2月に行われたRSA-250（829ビット、250桁の10進数）です。総計算時間は、Intel Xeon Gold 6130（2.1GHz）を使用した場合、約2700コア年でした。近年の因数分解記録と同様に、この因数分解は、一般数体ふるいの高度に最適化された実装を数百台のマシンで実行することで完了しました。

時間計算量

すべての整数を多項式時間で因数分解できるアルゴリズム、すなわち、ある定数kに対してbビット数n をO ( bk )時間で因数分解できるアルゴリズムは未だ発表されていない。そのようなアルゴリズムの存在も非存在も証明されていないが、一般的には存在しないと疑われている。[ 4 ] [ 5 ]

すべての正のεに対してO((1 +  ε ) b )より高速な、つまり指数関数的ではないアルゴリズムが公開されています。2022年現在、理論的に漸近実行時間が最も短いアルゴリズムは、1993年に初めて公開された一般数体ふるい（GNFS）であり、[ 6 ] bビット数nに対して実行時間で次のようになります。

経験⁡（（（83）23+o（1））（ログ⁡n）13（ログ⁡ログ⁡n）23）。{\displaystyle \exp \left(\left(\left(\left({\tfrac {8}{3}}\right)^{\frac {2}{3}}+o(1)\right)\left(\log n\right)^{\frac {1}{3}}\left(\log \log n\right)^{\frac {2}{3}}\right).}

現在のコンピュータでは、GNFSは大きなn（約400ビット以上）に対して公開されている最良のアルゴリズムです。しかし、量子コンピュータにおいては、ピーター・ショアが1994年に多項式時間でこれを解くアルゴリズムを発見しました。ショアのアルゴリズムは、bビットの数値入力に対して、わずかO( b 3 )の時間とO( b )の空間しか必要としません。2001年、ショアのアルゴリズムは、7量子ビットを提供する分子に対してNMR技術を用いて初めて実装されました。[ 7 ]

P、NP、co-NP などの複雑性クラスについて話すには、問題を決定問題として表現する必要があります。

決定問題 (整数因数分解) —すべての自然数およびに対して、nには1 以外に kより小さい因数がありますか?n{\displaystyle n}け{\displaystyle k}

これはNPとco-NPの両方であることが知られており、つまり「はい」と「いいえ」の両方の答えが多項式時間で検証できることを意味します。「はい」という答えは、因数分解n = d（⁠n/d⁠）で、 d ≤ kです。答えが「いいえ」であることは、 nをkより大きい異なる素数に因数分解することを示すことで証明できます。AKS素数判定法を使用して素数であることを確認し、それらを掛け合わせてnを得ることができます。算術の基本定理は、受け入れられる増加する素数の文字列は1つだけであることを保証し、これは問題がUPとco-UPの両方に存在することを示しています。 [ 8 ]ショアのアルゴリズムにより、 BQPに存在することが知られています

この問題は、P、NP完全、 [ 9 ]、および共NP完全の3つの複雑性クラスのいずれにも該当しないと考えられています。したがって、この問題はNP中間複雑性クラスの候補となります。

対照的に、「 nは合成数か？」（あるいは「nは素数か？」）という判定問題は、nの因数を特定する問題よりもはるかに容易であるように思われる。合成数／素数問題は、AKS素数判定を用いて多項式時間（ nの桁数bにおいて）で解くことができる。さらに、誤差の可能性が極めて小さいと許容できるのであれば、実用上非常に高速に素数判定できる確率アルゴリズムもいくつか存在する。素数判定の容易さはRSAアルゴリズムの重要な部分であり、まず大きな素数を見つける必要があるためである。

因数分解アルゴリズム

特殊用途

特殊目的の因数分解アルゴリズムの実行時間は、因数分解される数値の特性、またはその未知の因数の 1 つ (サイズ、特殊な形式など) によって異なります。実行時間を決定するパラメーターは、アルゴリズムによって異なります。

特殊目的の因数分解アルゴリズムの重要なサブクラスは、カテゴリ1または第一カテゴリのアルゴリズムであり、その実行時間は最小の素因数の大きさに依存します。未知の形式の整数が与えられた場合、これらの手法は通常、汎用的な手法よりも先に小さな因数を除去するために適用されます。[ 10 ]例えば、単純な試行除算はカテゴリ1のアルゴリズムです。

汎用

汎用因数分解アルゴリズム（カテゴリ2、第2カテゴリ、またはKraitchik族アルゴリズムとも呼ばれる）[ 10 ]の実行時間は、因数分解する整数の大きさにのみ依存します。これはRSA番号の因数分解に使用されるアルゴリズムです。ほとんどの汎用因数分解アルゴリズムは、平方合同法に基づいています。

その他の注目すべきアルゴリズム

ヒューリスティック実行時間

数論では、経験的に期待実行時間を持つ整数因数分解アルゴリズムが多数存在する。

Ln[12、1+o（1）]＝e（1+o（1））（ログ⁡n）（ログ⁡ログ⁡n）{\displaystyle L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}}

リトルO記法とL記法で記述される。これらのアルゴリズムの例としては、楕円曲線法や二次ふるい法などがある。また、類群関係法はSchnorr [ 11 ]、Seysen [ 12 ]、Lenstra [ 13 ]によって提案されたが、彼らは未証明の一般化リーマン予想のみを仮定して証明した。

厳格な実行時間

シュノア・セイセン・レンストラ確率アルゴリズムは、レンストラとポメランス[ 14 ]によって厳密に証明されており、期待実行時間L n [ ⁠1/2GRH仮定を乗数に置き換えることで、[⁠ , 1+ o (1)] を導出する。このアルゴリズムは、判別式Δの正二項二次形式の類群G Δを用いる。G Δは、互いに素である 整数の組( a , b , c )の集合である

Schnorr-Seysen-Lenstra アルゴリズム

因数分解される整数nが与えられます。ここでnは特定の定数より大きい奇数の正の整数です。この因数分解アルゴリズムでは、判別式Δはnの倍数、すなわちΔ = − dnとして選択されます。ここでdは正の乗数です。このアルゴリズムでは、1つのdに対して、 G Δに十分な数の滑らかな形式が存在すると想定されます。LenstraとPomeranceは、滑らかな結果を保証するために、 dの選択を小さな集合に制限できることを示しました。

クロネッカー記号( ⁠​​​​​Δ/q⁠ ) = 1 。G Δの生成元集合とqがP Δに属するG Δの素形式f qを構築することにより、生成元集合とf qの関係の列が生成される。q の大きさは、ある定数c 0 に対して c 0 ( log | Δ |) 2で制限される。

ここで用いる関係は、G Δの中立元に等しいべき乗の積の関係である。これらの関係を用いて、 G Δのいわゆる曖昧形式、すなわち 2 を割り切る位のG Δの元を構築する。Δ の対応する因数分解を計算し、最大公約数を求めることで、この曖昧形式からnの完全な素因数分解が得られる。このアルゴリズムは、主に以下のステップで構成される。

nを因数分解する数とします 。

  1. Δ を負の整数とし、Δ = − dnとします。ここで、 dは乗数、Δはある二次形式の負の判別式です。
  2. いくつかのt ∈ Nに対して、最初のt個の素数p 1 = 2、p 2 = 3、p 3 = 5、...、p t を取ります。
  3. f q をG Δのランダム素形式とし、 ( ⁠Δ/q⁠ ) = 1。
  4. G Δの生成集合Xを見つけます。
  5. 集合Xと{ f q  : q ∈ P Δ }の間の関係の列を収集し、次を満たす:
    （∏×∈X×r（×））。（∏q∈PΔfqt（q））＝1.{\displaystyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1.}
  6. 2を割り切る位数の元f ∈ G Δである曖昧形式( a , b , c )を構築し、 Δ = −4 acまたはΔ = a ( a − 4 c )またはΔ = ( b − 2 a )( b + 2 a )となるΔの最大奇数約数の互いに素な因数分解を取得します。
  7. 曖昧形式がnの因数分解を与える場合はそこで終了し、そうでない場合はnの因数分解が見つかるまで別の曖昧形式を探し続ける。無駄な曖昧形式が生成されないように、 G (Δ)の2-シロー群Sll 2 (Δ)を構築する。

任意の正の整数を因数分解するアルゴリズムを得るには、このアルゴリズムに試し割りやヤコビ和テストなどのいくつかのステップを追加する必要があります。

予想実行時間

このアルゴリズムは、ランダムな選択を行うため、確率的アルゴリズムである。その期待実行時間は最大でL n [ ⁠1/2⁠ , 1+ o (1)] . [ 14 ]

参照

注記

  1. ^ Lenstra、Arjen K. (2011)、「Integer Factoring」、カリフォルニア州ヘンク、van Tilborg。 Jajodia、Sushil (編)、Encyclopedia of Cryptography and Security、ボストン: Springer、pp.  611–618、doi : 10.1007/978-1-4419-5906-5_455、ISBN 978-1-4419-5905-8
  2. ^ 「[Cado-nfs-discuss] 795ビット因数分解と離散対数」 。2019年12月2日時点のオリジナルよりアーカイブ。
  3. ^クラインジュン、トルステン;青木一麿；フランケ、イェンス。レンストラ、アリエン K.トメ、エマニュエル。ボス、ジョッペ W.ゴードリー、ピリック。クルッパ、アレクサンダー。モンゴメリー、ピーター L.オスヴィック、ダグ・アーン。テ・リーレ、ハーマン・JJ。ティモフェエフ、アンドレイ。ポール・ジマーマン (2010)。「768 ビット RSA モジュラスの因数分解」(PDF)。ラビン、タル編（編）。暗号学の進歩 - CRYPTO 2010、第 30 回年次暗号会議、米国カリフォルニア州サンタバーバラ、2010 年 8 月 15 ～ 19 日。コンピューターサイエンスの講義ノート。 Vol. 6223.スプリンガー。 pp.  333–350。土井: 10.1007/978-3-642-14623-7_18。ISBN 978-3-642-14622-0。
  4. ^クランツ、スティーブン・G.（2011）、証明はプディングの中に：数学的証明の変化する性質、ニューヨーク：シュプリンガー、p. 203、doi：10.1007 / 978-0-387-48744-1、ISBN 978-0-387-48908-7、MR  2789493
  5. ^ Arora, Sanjeev ; Barak, Boaz (2009),計算複雑性, Cambridge: Cambridge University Press, p. 230, doi : 10.1017/CBO9780511804090 , ISBN 978-0-521-42426-4、MR  2500087、S2CID  215746906
  6. ^ Buhler, JP; Lenstra, HW Jr.; Pomerance, Carl (1993). 「数体ふるいを用いた整数の因数分解」.数体ふるいの開発. 数学講義ノート. 第1554巻. Springer. pp.  50– 94. doi : 10.1007/BFb0091539 . hdl : 1887/2149 . ISBN 978-3-540-57013-4. 2021年3月12日閲覧。
  7. ^ Vandersypen, Lieven MK; et al. (2001). 「核磁気共鳴を用いたショアの量子因数分解アルゴリズムの実験的実現」Nature . 414 (6866): 883– 887. arXiv : quant-ph/0112176 . Bibcode : 2001Natur.414..883V . doi : 10.1038/414883a . PMID 11780055 . S2CID 4400832 .  
  8. ^ Lance Fortnow (2002年9月13日). 「計算複雑性ブログ：今週の計算複雑性クラス：因数分解」 .
  9. ^ Goldreich, Oded ; Wigderson, Avi (2008)、「IV.20 計算複雑性」、Gowers, Timothy ; Barrow-Green, June ; Leader, Imre (eds.)、The Princeton Companion to Mathematics、プリンストン大学出版局、  575–604頁、ISBN 978-0-691-11880-2、MR  2467561特に583ページを参照。
  10. ^ a bデイヴィッド・ブレソウドとスタン・ワゴン(2000). 『計算数論講座』 . Key College Publishing/Springer. pp.  168–69 . ISBN 978-1-930190-10-8。
  11. ^ Schnorr, Claus P. (1982). 「いくつかの因数分解アルゴリズムの改良と解析」 . Journal of Algorithms . 3 (2): 101– 127. doi : 10.1016/0196-6774(82)90012-8 . MR 0657269. 2017年9月24日時点のオリジナルよりアーカイブ。 
  12. ^ Seysen, Martin (1987). 「負の判別式の二次形式を用いた確率的因数分解アルゴリズム」 .計算数学. 48 (178): 757– 780. doi : 10.1090/S0025-5718-1987-0878705-X . MR 0878705 . 
  13. ^ Lenstra, Arjen K (1988). 「一般化リーマン予想に基づく高速かつ厳密な因数分解」(PDF) . Indagationes Mathematicae . 50 (4): 443– 454. doi : 10.1016/S1385-7258(88)80022-2 .
  14. ^ a b Lenstra, HW; Pomerance, Carl (1992年7月). 「整数因数分解の厳密な時間境界」(PDF) .アメリカ数学会誌. 5 (3): 483– 516. doi : 10.1090/S0894-0347-1992-1137100-0 . MR 1137100 . 

参考文献

「 https://en.wikipedia.org/w/index.php?title=Integer_factorization&oldid=1334546942」より取得