導入
二次ふるいアルゴリズムは、モジュラー演算に基づく因数分解アルゴリズムです。実際には、これは数値フィールドでの一般化されたスクリーニングの後で最も高速ですが、はるかに複雑で、少なくとも 10 進数 100 桁の整数を因数分解する場合にのみ効率的です。二次ふるいは、特殊化されていない因数分解アルゴリズムです。つまり、その実行時間は因数分解される整数のサイズのみに依存し、整数の特定のプロパティには依存しません。
基本目標
1981 年に Carl Pomerance によって開発されたこのアルゴリズムは、Dixon の因数分解法を改良したもので、それ自体はフェルマーの因数分解法に基づいています。 n (因数分解される整数) を法とする二乗の合同を確立しようとします。これは、多くの場合、次の因数分解につながります。 n 。
このアルゴリズムは 2 つのフェーズで動作します。
- データ収集フェーズでは、正方形の合同につながる可能性のある情報を収集します。
- データ活用フェーズでは、収集したすべてのデータを行列に配置し、それを解いて正方形の合同を求めます。
収集フェーズは簡単かつ効率的に並列化できますが、活用フェーズは並列化できません。ただし、サブシステムの数が少なく、それぞれのサブシステムに行列全体を格納するのに十分なメモリがある場合を除きます (この場合、 Wiedemann ブロック アルゴリズムを使用できます)。
平方の合同を見つける素朴なアプローチは、数値をランダムに選択し、それを平方し、 nを法とした最小の剰余 (正またはゼロ) が完全な平方(つまり、全体の 2 乗) であることを期待することです。たとえば、モジュロ 5959 では、整数 80 2は 441=21 2に一致します。 nが大きい場合、このアプローチで平方の合同が見つかることはめったにありませんが、これが発生した場合、この合同はほとんどの場合自明ではないため、 n を因数分解することができます。
整数n を因数分解する二次ふるいの実行時間は次のとおりです。
- $$ {O\left(e^\sqrt{\log n \log\log n}\right)=L_n\left[1/2,1\right]} $$
Landau の O 記法とL 記法を使用します。
複数の多項式
実際には、単一の多項式y ( x ) = x2 − nでは、因子に基づく十分な正規 ( x , y ) が得られません。次に、多項式の族全体を使用します。 nを法とする平方になるには、元の多項式と同様の形式でなければなりません。
- $$ {y(x)=(Ax+B)^2-n \qquad A,B\in\mathbb{Z}~.} $$
このアプローチは、多重多項式二次スクリーニングと呼ばれ、並列化に最適です。
合同式の探索の最適化
二次ふるいは、 x 2 ≡ y 2 (mod n ) よりもはるかに弱い条件を満たす、整数xとy(x) ( y(x)はxの関数) のペアを見つけようとします。これは、 factor Baseと呼ばれる素数のセットを選択し、 nを法とするx 2の「最小絶対剰余」 y(x)がこの「base」で完全に因数分解されるxを探します。このような整数のペアは、この基数に対して規則的であると言われ、基数でのy(x)の因数分解とxの値の組み合わせは、いわゆる関係を構成します。二次ふるいは、 x をnの平方根に近づけることにより、関係を見つけるプロセスを高速化します。したがって、 y(x) は小さくなり、したがって「正規」である可能性が高くなります。 x =[√ n ]+ z ( z整数が「小さい」) の場合、
ただし、これはy がzに応じて線形に増加することも意味します。
整合性の可能性を高めるもう 1 つの方法は、単純にデータベースのサイズを増やすことですが、これにはより多くの関係を収集する必要があります。実際、関係が線形依存していることを確認するには、基底の素因数の数より少なくとも 1 つ多くなければなりません。
部分的な関係とサイクル
関係においてy(x) が規則的でない場合でも、そのような 2 つの部分関係をマージすることによって「完全な」関係が形成されることがあります。これが起こるためには、基底の外側で 2 つの素因数が同じである必要があります。たとえば、基数が {2, 3, 5, 7} でn = 91 の場合、2 つの部分関係の積は次のようになります。
- $$ {21^2\equiv7^1\cdot11\pmod{91}} $$そして
- $$ {29^2\equiv2^1\cdot11\pmod{91}} $$
私たちは得る
- $$ {(21\cdot 29)^2\equiv2^1\cdot7^1\cdot11^2\pmod{91}~.} $$
2 つの辺に 11 -1の 91 を法とする 2 乗、つまり 58 (たとえば、拡張Euclidアルゴリズムを使用して取得された値) を乗算することにより、完全な関係を推定します。
- $$ {(58\cdot 21\cdot 29)^2\equiv 2^1\cdot7^1\pmod{91}~,} $$どちらか
- $$ {14^2\equiv 2^1\cdot7^1\pmod{91}~.} $$
このような完全な関係（部分関係の組み合わせによって得られる）をサイクルと呼びます。場合によっては、2 つの部分関係からのサイクルの形成が正方形の合同に直接つながることがありますが、それはまれです。
スクリーニングによる規則性の確認
yの規則性を確認するにはいくつかの方法があります。最も明白なのは分割テスト方法ですが、これによりデータ収集フェーズの所要時間が増加します。楕円曲線法も時々使用される別の方法です。しかし、最も一般的な方法は、スクリーニングによって続行することです。
- $$ {y(x)=x^2-n\,\!} $$
- $$ {y(x+kp)=(x+kp)^2-n\,\!} $$
- $$ {y(x+kp)=x^2+2xkp+(kp)^2-n\,\!} $$
- $$ {y(x+kp)=y(x)+2xkp+(kp)^2\equiv y(x)\pmod{p}} $$
答えてください。y (x) ≡ 0 (mod p ) となるようなx がわかっている場合、 pで割り切れるyのシーケンス全体を推定します。 pの他の値に対してこのプロセスを繰り返すことで、毎回規則性をテストする必要がなく (この体系的なテストには時間がかかりすぎます)、スクリーニング プロセス (エラトステネスのふるいに似ています) を通じて規則的な値が見つかります。以下の因数分解レコードのような大きな数の場合)。このプロセス中に、収集された通常のyの因数分解の詳細な情報が失われますが、「小さな」因数 (基数の因数) しかないため、すぐに再計算できます。