整数因数分解

コンピュータサイエンスにおける未解決問題

整数因数分解は、古典的なコンピュータで多項式時間で解けるだろうか？

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

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

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

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

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

素因数分解

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

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

因数分解アルゴリズム

特殊用途

特殊な因数分解アルゴリズムの実行時間は、因数分解する数の特性、あるいは未知の因数（大きさ、特殊な形式など）に依存します。実行時間を決定するパラメータは、アルゴリズムによって異なります。

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

裁判部門
ホイールファクタリング
ポラードのローアルゴリズムには、群サイクルを識別するための2つの一般的なバージョンがあり、1つはフロイドによるもの、もう1つはブレントによるものです。
代数群分解アルゴリズムには、ポラードの $p - 1$ アルゴリズム、ウィリアムズの $p + 1$ アルゴリズム、レンストラ楕円曲線分解などがある。
フェルマーの因数分解法
オイラーの因数分解法
特殊番号フィールドふるい
2乗の差

汎用

汎用因数分解アルゴリズムは、カテゴリ 2、第 2 カテゴリ、またはKraitchikファミリーアルゴリズムとも呼ばれ、^{[ 10 ]}実行時間は因数分解する整数のサイズのみに依存します。これは、 RSA 番号の因数分解に使用されるタイプのアルゴリズムです。ほとんどの汎用因数分解アルゴリズムは、平方の合同法に基づいています。

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

量子コンピュータのためのショアのアルゴリズム

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

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

L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}

リトルオー記法とL記法で表されます。これらのアルゴリズムの例としては、楕円曲線法と二次篩法があります。また、Schnorr ^[¹¹^] Seysen ^[¹²^]および Lenstra ^[¹³^]によって提案されたクラス群関係法もそのようなアルゴリズムの一つで、彼らは未証明の一般化リーマン予想を仮定してこれを証明しました。

厳しい実行時間

Schnorr–Seysen–Lenstra 確率アルゴリズムは、GRH 仮定を乗数の使用に置き換えることにより、 Lenstra と Pomerance ^{[ 14 ]}によって期待実行時間が $L n [⁠ 1 / 2 ⁠, 1+ o (1)]であることが厳密に証明されています。このアルゴリズムは、$ 判別式Δ $の$ 正の二進二次形式のクラス群 $G$ $Δ$ $を$ 使用します。G $Δ$ は、互いに素である整数の 3 つ $($ $a$ $,$ $b$ $,$ $c$ $)$ の集合です。

Schnorr-Seysen-Lenstra アルゴリズム

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

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

使用する関係は、 $G$ $Δ$ の中立要素に等しいべき乗の積の関係です。これらの関係を使用して、 $G$ $Δ$ のいわゆる曖昧形式、つまり 2 を割り切る位数の $G$ $Δ$ の要素を構築します。Δ の対応する因数分解を計算し、 $最大公約数$ を取ることで、この曖昧形式は $n$ の完全な素因数分解を提供します。このアルゴリズムの主な手順は次のとおりです。

$n$ を因数分解する数とする。

$Δ を$ 負の整数とし、 $Δ = - dn$ とする。ここで $d$ は乗数であり、 $Δ$ はある二次形式の負の判別式である。
最初の $t個の素数$ $p 1 = 2、 p 2 = 3、 p 3 = 5、...、 p t$ 、ある $t \in N$ について、これらを取る。
$f q を$ $G Δ$ のランダムな素数形式とし、 $(⁠ Δ / q ⁠) = 1 と$ する。
$G$ $Δ$ の生成集合 $X$ を見つけます。
$集合X$ と ${f q : q \in P Δ}$ の間の関係のシーケンスを収集し、以下の条件を満たすものとする。
$\displaystyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1.}$
2 を割り切る位数の要素 $f$ $\in$ $G$ $Δ$ である曖昧な形式 $(a, b, c)を構築して、$ $Δ = -4$ $ac$ または $Δ =$ $a$ $($ $a$ $- 4$ $c$ $)$ または $Δ = ($ $b$ $- 2$ $a$ $)($ $b$ $+ 2$ $a$ $)$ となる $Δ$ の最大の奇数因子の互いに素な因数分解を取得します。
$曖昧な形式がn$ の因数分解を提供する場合は停止し、そうでない場合は $n$ の因数分解が見つかるまで別の曖昧な形式を探します。不要な曖昧な形式が生成されないように、 $G$ $(Δ)$ の2-シロー群 $Sll 2 (Δ)$ を構築します。

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

予想上映時間

前述のアルゴリズムは、ランダムな選択を行うため、確率的アルゴリズムです。期待される実行時間は最大で $L n [⁠ 1 / 2 ⁠, 1+ o (1)]$ です。^{[ 14 ]}

注記

↑ 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
↑ " [ Cado-nfs-discuss ] 795ビット因数分解と離散対数"。 2019年12月2日にオリジナルからアーカイブされました。
↑クラインジュン、トルステン。青木一麿；フランケ、イェンス。レンストラ、アリエン 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。
↑クランツ、スティーブン・G. (2011)、『証明はプディングの中にある：数学的証明の変容する性質』、ニューヨーク：スプリンガー、p. 203、doi：10.1007/978-0-387-48744-1、ISBN 978-0-387-48908-7MR 2789493
↑ Arora, Sanjeev ; Barak, Boaz (2009), Computational complexity , Cambridge: Cambridge University Press, p. 230, doi : 10.1017/CBO9780511804090 , ISBN 978-0-521-42426-4MR 2500087、S2CID 215746906
↑ Buhler, JP; Lenstra, HW Jr.; Pomerance, Carl (1993). "数体篩による整数の因数分解".数体篩の発展. Lecture Notes in Mathematics. Vol. 1554. Springer. pp. 50–94 . doi : 10.1007/BFb0091539 . hdl : 1887/2149 . ISBN 978-3-540-57013-42021年3月12日に取得。
↑ Vandersypen, Lieven MK; et al. (2001). "核磁気共鳴を用いたShorの量子因数分解アルゴリズムの実験的実現". Nature . 414 ( 6866): 883–887 . arXiv : quant-ph/0112176 . Bibcode : 2001Natur.414..883V . doi : 10.1038/414883a . PMID 11780055. S2CID 4400832 .
↑ Lance Fortnow (2002-09-13). "計算複雑性ブログ: 今週の複雑性クラス: 因数分解" .
↑ Goldreich, Oded ; Wigderson, Avi (2008)、「IV.20 計算複雑性」、Gowers, Timothy ; Barrow-Green, June ; Leader, Imre (編)、『The Princeton Companion to Mathematics』、プリンストン、ニュージャージー州：プリンストン大学出版局、pp. 575–604、ISBN 978-0-691-11880-2MR 2467561 特に583ページを参照。
1 2 David BressoudおよびStan Wagon (2000).計算数論入門. Key College Publishing/Springer. pp. 168–69 . ISBN 978-1-930190-10-8。
↑ Schnorr, Claus P. (1982). "Refined analysis and improvements on some factoring algorithms" . Journal of Algorithms . 3 (2): 101– 127. doi : 10.1016/0196-6774(82)90012-8 . MR 0657269. 2017年9月24日にオリジナルからアーカイブ済み。
↑ Seysen, Martin (1987). "負の判別式の二次形式を用いた確率的因数分解アルゴリズム" . Mathematics of Computation . 48 (178): 757–780 . doi : 10.1090/S0025-5718-1987-0878705-X . MR 0878705 .
↑ Lenstra, Arjen K (1988). "一般化リーマン予想の下での高速かつ厳密な因数分解" (PDF) . Indagationes Mathematicae . 50 (4): 443– 454. doi : 10.1016/S1385-7258(88)80022-2 .
1 2 Lenstra, HW; Pomerance, Carl (1992 年 7 月). "整数の因数分解に対する厳密な時間制限" (PDF) . Journal of the American Mathematical Society . 5 (3): 483– 516. doi : 10.1090/S0894-0347-1992-1137100-0 . MR 1137100 .

参考文献

リチャード・クランドール、カール・ポメランス（2001）。素数：計算論的視点。シュプリンガー。ISBN 0-387-94777-9。第5章：指数因数分解アルゴリズム、 191～226ページ。第6章：準指数因数分解アルゴリズム、227～284ページ。第7.4節：楕円曲線法、301～313ページ。
ドナルド・クヌース著『コンピュータプログラミングの技法』第2巻：半数値アルゴリズム、第3版。アディソン・ウェスリー、1997年。ISBN 0-201-89684-2セクション 4.5.4: 素因数分解、pp. 379–417。
サミュエル・S・ワグスタッフ・ジュニア（2013）。『因数分解の喜び』。プロビデンス、ロードアイランド州：アメリカ数学会。ISBN 978-1-4704-1048-3。。
ウォーレン、ヘンリー・S・ジュニア（2013）。ハッカーズ・ディライト（第2 版）。アディソン・ウェスリー-ピアソン・エデュケーション社。ISBN 978-0-321-84268-8。

外部リンク

msieve – SIQSおよびNFS – は、既知の最大規模の公開因数分解のいくつかを完了するのに役立ってきた。
リチャード・P・ブレント、「整数因数分解アルゴリズムの最近の進歩と展望」、Computing and Combinatorics、2000年、3～22ページ。ダウンロード
マニンドラ・アグラワル、ニーラージ・カヤル、ニティン・サクセナ、「PRIMES は P にあります。」 Annals of Mathematics 160(2): 781–793 (2004)。2005年8月版PDF
エリック・W・ワイススタイン、「RSA-640の因数分解」MathWorld Headline News、2005年11月8日
ダリオ・アルパーンの整数因数分解計算機– 大きな整数を因数分解するためのウェブアプリ

[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日にオリジナルからアーカイブされました。

[rsa768-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-7MR 2789493

[5] Arora, Sanjeev ; Barak, Boaz (2009), Computational complexity , Cambridge: Cambridge University Press, p. 230, doi : 10.1017/CBO9780511804090 , ISBN 978-0-521-42426-4MR 2500087、S2CID 215746906

[6] Buhler, JP; Lenstra, HW Jr.; Pomerance, Carl (1993). "数体篩による整数の因数分解".数体篩の発展. Lecture Notes in Mathematics. Vol. 1554. Springer. pp. 50–94 . doi : 10.1007/BFb0091539 . hdl : 1887/2149 . ISBN 978-3-540-57013-42021年3月12日に取得。

[7] Vandersypen, Lieven MK; et al. (2001). "核磁気共鳴を用いたShorの量子因数分解アルゴリズムの実験的実現". 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-09-13). "計算複雑性ブログ: 今週の複雑性クラス: 因数分解" .

[9] Goldreich, Oded ; Wigderson, Avi (2008)、「IV.20 計算複雑性」、Gowers, Timothy ; Barrow-Green, June ; Leader, Imre (編)、『The Princeton Companion to Mathematics』、プリンストン、ニュージャージー州：プリンストン大学出版局、pp. 575–604、ISBN 978-0-691-11880-2MR 2467561 特に583ページを参照。

[Bressoud_and_Wagon-10] 1 2 David BressoudおよびStan Wagon (2000).計算数論入門. Key College Publishing/Springer. pp. 168–69 . ISBN 978-1-930190-10-8。

[1982-schnorr-11] Schnorr, Claus P. (1982). "Refined analysis and improvements on some factoring algorithms" . Journal of Algorithms . 3 (2): 101– 127. doi : 10.1016/0196-6774(82)90012-8 . MR 0657269. 2017年9月24日にオリジナルからアーカイブ済み。

[1987-seysen-12] Seysen, Martin (1987). "負の判別式の二次形式を用いた確率的因数分解アルゴリズム" . Mathematics of Computation . 48 (178): 757–780 . doi : 10.1090/S0025-5718-1987-0878705-X . MR 0878705 .

[1988-lenstra-13] Lenstra, Arjen K (1988). "一般化リーマン予想の下での高速かつ厳密な因数分解" (PDF) . Indagationes Mathematicae . 50 (4): 443– 454. doi : 10.1016/S1385-7258(88)80022-2 .

[lenstra-pomerance-14] 1 2 Lenstra, HW; Pomerance, Carl (1992 年 7 月). "整数の因数分解に対する厳密な時間制限" (PDF) . Journal of the American Mathematical Society . 5 (3): 483– 516. doi : 10.1090/S0894-0347-1992-1137100-0 . MR 1137100 .

[

[

[

[

[

[ 6 ]

[

[

この問題は、複雑性クラス P、NP 完全、 [ 9 ]

[ 10 ]

[

[

[

[ 14 ]