整数因数分解

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

古典的なコンピュータで整数因数分解を多項式時間で解くことはできますか?

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

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

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

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

多くの暗号化プロトコルは、大きな合成整数を因数分解することの難しさや、それに関連する問題（たとえば、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 倍であるため、合成数を因数分解するのにはるかに長い時間がかかります。

現在の最先端技術

$b$ ビットの数値のうち、既存のアルゴリズムを使用して実際に因数分解するのが最も難しいのは、因数が同様のサイズである半素数です。このため、暗号化アプリケーションではこれらの整数が使用されます。

2019年、Fabrice Boudot、Pierrick Gaudry、Aurore Guillevic、Nadia Heninger、Emmanuel Thomé、Paul Zimmermannは、約900コア年の計算能力を駆使して、 240桁（795ビット）の数（ RSA-240 ）を因数分解しました。 ^[2]研究者らは、1024ビットのRSA法には約500倍の時間がかかると推定しました。^[3]

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

時間計算量

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

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

\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(b3)の$ 時間と $O(b)の$ 空間しかかからない。2001年に、ショアのアルゴリズムは、 7量子ビットを提供する分子に対してNMR技術を使用することで初めて実装された。 ^[7]

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

決定問題 (整数因数分解) — すべての自然数およびに対して、 $n に$ は 1 以外に $k$ より小さい因数があるでしょうか? $n$ $k$

これはNPとco-NP の両方であることが知られており、つまり「はい」と「いいえ」の両方の答えを多項式時間で検証できることを意味します。「はい」の答えは因数分解 $n = d ( .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ん/d⁠）$ で $、 d \leq 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または第1カテゴリのアルゴリズムであり、その実行時間は最小の素因数のサイズに依存します。未知の形式の整数が与えられた場合、これらの方法は通常、小さな因数を除去するための汎用方法の前に適用されます。^[10]たとえば、単純な試行除算はカテゴリ1アルゴリズムです。

裁判部
ホイール分解
Pollard の rho アルゴリズムには、グループサイクルを識別するための 2 つの一般的な種類があります。1 つは Floyd によるもので、もう 1 つは Brent によるものです。
代数群因数分解アルゴリズム。その中には、ポラードの $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)}}}

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

厳しい実行時間

シュノア・セイセン・レンストラ確率アルゴリズムは、レンストラとポメランス^[14]によって厳密に証明されており、期待実行時間 $L n [⁠ 1 / 2$ GRH仮定を乗数の使用に置き換えることで、 $⁠$ $, 1+$ $o$ $(1)] を実現できます。このアルゴリズムでは、$ 判別式 $Δ$ の正の2進二次形式の類群 $G$ $Δ$ を使用します。G $Δ は、$ $互いに素$ である整数 $の3つ組($ $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$ $Δ$ の要素)を構築するために使用されます。 $Δ$ の対応する因数分解を計算し、 gcdを取ることで、このあいまいな形式は $n$ の完全な素因数分解を提供します。このアルゴリズムには、次の主な手順があります。

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

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

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

予想実行時間

このアルゴリズムはランダムな選択を行う確率的アルゴリズムです。その予想される実行時間は最大で $L n [⁠ 1 / 2 ⁠, 1+ o (1)]$ .^[14]

参照

オーリフィーユ因数分解
因数分解による乱数生成のためのバッハのアルゴリズム
正の整数の正規表現
因数分解
乗法分割
$p$ 進評価
整数分割– 数値を正の整数の合計として表す方法。

注記

^ Lenstra、Arjen K. (2011)、「Integer Factoring」、カリフォルニア州ヘンク、van Tilborg。 Jajodia、Sushil (編)、Encyclopedia of Cryptography and Security、ボストン、マサチューセッツ州: Springer US、pp. 611–618、doi :10.1007/978-1-4419-5906-5_455、ISBN 978-1-4419-5905-8、 2022年6月22日取得
^ 「[Cado-nfs-discuss] 795 ビット因数分解と離散対数」。2019 年 12 月 2 日時点のオリジナルよりアーカイブ。
^ クラインユング、トルステン;青木一麿；フランケ、イェンス。レンストラ、アリエン K.トメ、エマニュエル。ボス、ジョッペ W.ゴードリー、ピリック。クルッパ、アレクサンダー。モンゴメリー、ピーター L.オスヴィック、ダグ・アーン。テ・リーレ、ハーマン・JJ。ティモフェエフ、アンドレイ。ポール・ジマーマン (2010)。「768 ビット RSA モジュラスの因数分解」(PDF)。ラビン、タル編（編）。暗号学の進歩 - CRYPTO 2010、第 30 回年次暗号会議、米国カリフォルニア州サンタバーバラ、2010 年 8 月 15 ～ 19 日。コンピューターサイエンスの講義ノート。 Vol. 6223.スプリンガー。 333–350ページ。doi :10.1007/978-3-642-14623-7_18.
^ クランツ、スティーブン・G. (2011)、証明はプディングの中に：数学的証明の変化する性質、ニューヨーク：シュプリンガー、p. 203、doi：10.1007 / 978-0-387-48744-1、ISBN 978-0-387-48908-7、MR 2789493
^ アローラ、サンジーヴ、バラク、ボアズ（2009）、計算複雑性、ケンブリッジ：ケンブリッジ大学出版局、p. 230、doi：10.1017 / CBO9780511804090、ISBN 978-0-521-42426-4、MR 2500087、S2CID 215746906
^ 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日閲覧。
^ 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.
^ Lance Fortnow (2002-09-13). 「計算複雑性ブログ: 今週の複雑性クラス: 因数分解」
^ Goldreich, Oded ; Wigderson, Avi (2008)、「IV.20 計算複雑性」、Gowers, Timothy ; Barrow-Green, June ; Leader, Imre (eds.)、The Princeton Companion to Mathematics、プリンストン、ニュージャージー：プリンストン大学出版局、pp. 575–604、ISBN 978-0-691-11880-2、MR 2467561特に583ページを参照。
^ ab David BressoudおよびStan Wagon (2000)。計算数論講座。Key College Publishing/ Springer。pp . 168–69。ISBN 978-1-930190-10-8。
^ Schnorr, Claus P. (1982). 「いくつかの因数分解アルゴリズムの改良分析と改善」Journal of Algorithms . 3 (2): 101–127. doi :10.1016/0196-6774(82)90012-8. MR 0657269. 2017年9月24日時点のオリジナルよりアーカイブ。
^ Seysen, Martin (1987). 「負の判別式の二次形式による確率的因数分解アルゴリズム」.計算数学. 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.
^ ab 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 章: 指数因数分解アルゴリズム、pp. 191–226。第 6 章: 準指数因数分解アルゴリズム、pp. 227–284。セクション 7.4: 楕円曲線法、pp. 301–313。
ドナルド・クヌース。『コンピュータプログラミングの芸術』第2巻：半数値アルゴリズム、第3版。Addison-Wesley、1997年。ISBN 0-201-89684-2。セクション4.5.4：素因数分解、pp. 379–417 。
サミュエル・S・ワグスタッフ・ジュニア（2013年）『因数分解の喜び』プロビデンス、ロードアイランド州：アメリカ数学協会。ISBN 978-1-4704-1048-3。。
ウォーレン、ヘンリー S. ジュニア (2013)。Hacker 's Delight (第 2 版)。Addison Wesley - Pearson Education、Inc. ISBN 978-0-321-84268-8。

外部リンク

msieve（SIQSとNFS）は、知られている最大の公開因数分解のいくつかを完成させるのに役立っています。
Richard P. Brent、「整数因数分解アルゴリズムの最近の進歩と展望」、Computing and Combinatorics、2000 年、3 ～ 22 ページ。ダウンロード
マニンドラ・アグラワル、ニーラージ・カヤル、ニティン・サクセナ、「PRIMES は P にあります。」 Annals of Mathematics 160(2): 781–793 (2004)。 2005年8月版PDF
Eric W. Weisstein、「RSA-640 の因数分解」MathWorld ヘッドラインニュース、2005 年 11 月 8 日
Dario Alpern の整数因数分解計算機 – 大きな整数を因数分解する Web アプリ

[1] Lenstra、Arjen K. (2011)、「Integer Factoring」、カリフォルニア州ヘンク、van Tilborg。 Jajodia、Sushil (編)、Encyclopedia of Cryptography and Security、ボストン、マサチューセッツ州: Springer US、pp. 611–618、doi :10.1007/978-1-4419-5906-5_455、ISBN 978-1-4419-5905-8、 2022年6月22日取得

[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.スプリンガー。 333–350ページ。doi :10.1007/978-3-642-14623-7_18.

[4] クランツ、スティーブン・G. (2011)、証明はプディングの中に：数学的証明の変化する性質、ニューヨーク：シュプリンガー、p. 203、doi：10.1007 / 978-0-387-48744-1、ISBN 978-0-387-48908-7、MR 2789493

[5] アローラ、サンジーヴ、バラク、ボアズ（2009）、計算複雑性、ケンブリッジ：ケンブリッジ大学出版局、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-09-13). 「計算複雑性ブログ: 今週の複雑性クラス: 因数分解」

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

[Bressoud_and_Wagon-10] 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). 「いくつかの因数分解アルゴリズムの改良分析と改善」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). 「負の判別式の二次形式による確率的因数分解アルゴリズム」.計算数学. 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] 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.