二次ふるい

二次ふるい 法( QS ) は整数因数分解アルゴリズムであり、実際には、一般数体ふるい法に次いで 2 番目に高速な方法として知られています。100 桁程度の小数点以下の整数に対しては依然として最速であり、数体ふるい法よりもかなり単純です。これは汎用の因数分解アルゴリズムであり、実行時間は因数分解する整数のサイズのみに依存し、特殊な構造や特性には依存しません。これは、 1981 年にカール・ポメランスがシュロッペルの線形ふるい法の改良として発明しました。 ^[1]

このアルゴリズムは、 n (因数分解する整数) を法として平方合同を設定しようとしますが、多くの場合、 n の因数分解につながります。アルゴリズム は2つのフェーズで動作します。1 つは平方合同につながる可能性のある情報を収集するデータ収集フェーズ、もう1つは収集したすべてのデータを行列に入れて解き、平方合同を取得します。データ収集フェーズは、多くのプロセッサに簡単に並列化できますが、データ処理フェーズには大量のメモリが必要であり、多くのノードで効率的に並列化したり、処理ノードごとに行列全体を格納するのに十分なメモリがない場合は、並列化が困難です。ブロック ヴィーデマン アルゴリズムは、それぞれが行列を保持できるシステムが少数ある場合に使用できます。

平方の合同を求める単純な方法は、ランダムな数を選び、それを二乗し、nで割り、最小の非負の余りが完全な平方になることを期待することです。たとえば、 です。この方法では、大きなnに対して平方の合同が見つかることはまれですが、見つかった場合は、大抵の場合、合同は自明ではなく、因数分解は完全です。これがフェルマーの因数分解法の大まかな基礎です。 ${\displaystyle 80^{2}\equiv 441=21^{2}{\pmod {5959}}}$

二次ふるいはディクソンの因数分解法の改良版である。二次ふるい（整数nを因数分解する） に必要な一般的な実行時間は、

${\displaystyle e^{(1+o(1)){\sqrt {\ln n\ln \ln n}}}=L_{n}\left[1/2,1\right]}$

L表記では ^[2]定数eは自然対数の底である。

フェルマーの方法で整数n を因数分解するには、a ^2をnで割った余りが平方になるような単一の数a （ n 1/2 ^< a < n −1）を探す必要があります。しかし、このようなa を見つけるのは困難です。二次ふるいは、いくつかのaについてa ² / nの余りを計算し、積が平方になるこれらの部分集合を見つけることです。これにより、平方数の合同が得られます。

例えば、1649という数を因数分解してみると、次のようになります。どの整数も平方数ではありませんが、積は平方数になります。また、 ${\displaystyle 41^{2}\equiv 32,42^{2}\equiv 115,43^{2}\equiv 200{\pmod {1649}}}$${\displaystyle 32,115,200}$${\displaystyle 32\cdot 200=80^{2}}$

${\displaystyle 32\cdot 200\equiv 41^{2}\cdot 43^{2}=(41\cdot 43)^{2}\equiv 114^{2}{\pmod {1649}}}$

であるからである。このようにして正方形の合同が得られる観察${\displaystyle 41\cdot 43\equiv 114{\pmod {1649}}}$${\displaystyle 32\cdot 200=80^{2}}$

${\displaystyle 114^{2}\equiv 80^{2}{\pmod {1649}}.}$

したがって、ある整数に対して、因数分解できる。 ${\displaystyle 114^{2}-80^{2}=(114+80)\cdot (114-80)=194\cdot 34=k\cdot 1649}$${\displaystyle k}$

${\displaystyle 1649=\gcd(194,1649)\cdot \gcd(34,1649)=97\cdot 17}$

ユークリッドの互除法を使用して最大公約数を計算します。

これで問題は次のように簡略化されました。整数の集合が与えられた場合、その積が平方になるような部分集合を見つけます。算術の基本定理により、任意の正の整数は、素数累乗の積として一意に表すことができます。これをベクトル形式で行います。たとえば、504 の素数累乗は 2 ³ 3 ² 5 ⁰ 7 ¹なので、指数ベクトル (3,2,0,1) で表されます。2 つの整数を乗算することは、それらの指数ベクトルを加算することに相当します。指数ベクトルがすべての座標で偶数である場合、その数は平方です。たとえば、ベクトル (3,2,0,1) + (1,0,0,1) = (4,2,0,2) なので、(504)(14) は平方です。平方数を求めるには、ベクトル内の数値の偶奇性に関する知識のみが必要なので、これらのベクトルを mod 2 で計算するだけで十分です: (1,0,0,1) + (1,0,0,1) = (0,0,0,0)。したがって、(0,1) ベクトルのセットが与えられた場合、ゼロ ベクトルをmod 2で加算するサブセットを見つける必要があります。

これは線型代数の問題です。環は 2 次ガロア体とみなすことができるため、つまり、2 を法として計算するときに、すべての非ゼロ数 (存在するのは 1 のみ) で割ることができるからです。線型代数の定理では、各ベクトルの要素数よりもベクトルの数が多い場合、常に線形従属関係が存在するということです。これはガウスの消去法で見つけることができます。しかし、多くの乱数を mod n で単純に 2 乗すると、非常に多くの異なる素因数が生成され、非常に長いベクトルと非常に大きな行列が生成されます。秘訣は、特にa ² mod n が小さな素因数だけを持つような数aを探すことです (これらは滑らかな数です)。これらは見つけるのが困難ですが、滑らかな数だけを使用すると、ベクトルと行列をより小さく扱いやすく保つことができます。二次ふるいは、後で説明するふるい分けと呼ばれる手法を使用して滑らかな数を検索します。このアルゴリズムの名前の由来はここにあります。 ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$

要約すると、基本的な二次ふるいアルゴリズムには次の主なステップがあります。

1. 滑らかさの境界 Bを選択します。 Bより小さい素数の数を表す数 π( B ) は、ベクトルの長さと必要なベクトルの数の両方を制御します。
2. ふるい分けを使用して、b _i = ( a _i ² mod n ) がB滑らかであるようなπ( B ) + 1 個の数a _iを見つけます。
3. b _{i を}因数分解し、それぞれに対して 2 を法とする指数ベクトルを生成します。
4. 線形代数を使用して、ゼロ ベクトルに加算されるこれらのベクトルのサブセットを見つけます。対応するa _{i を} 掛け合わせて、 n を法とする結果にaという名前を付けます。同様に、b _{i を}掛け合わせると、B滑らかな平方 b ²が生成されます。
5. ここで、等式a ² = b ² mod nが残り、ここから ( a ² mod n ) の 2 つの平方根が得られます。1 つはb ²の整数 b の平方根をとり、もう1 つは手順 4 で計算したaです。
6. これで、目的の恒等式が得られます。aとbの差 (または和) を持つnの GCD を計算します。これにより因数が生成されますが、これは単純な因数 ( nまたは 1) である可能性があります。因数が単純な場合は、異なる線形依存関係または異なるaで再試行してください。${\displaystyle (a+b)(a-b)\equiv 0{\pmod {n}}}$

この記事の残りの部分では、この基本アルゴリズムの詳細と拡張について説明します。

二次ふるいは、x ² ≡ y ² (mod n ) よりもはるかに弱い条件を満たす整数 x と y ( x ) (ただし y ( x ) は x の関数) のペアを見つけようとします。これは、因数基数と呼ばれる素数の集合を選択し、 y ( x ) = x 2 mod nの最小絶対剰余が因数基数で完全に因数分解されるようなx を見つけようとします。このようなy^値は、因数基数に関して滑らかで あると言われています。

y ( x )の値を因数分解して、因数基数で分解したものをxの値とともに関係式といいます。二次ふるいは、 x をnの平方根に近づけることで、関係式を見つけるプロセスを高速化します。これにより、y ( x ) が小さくなり、滑らかになる可能性が高くなります。

${\displaystyle y(x)=\left(\left\lceil {\sqrt {n}}\right\rceil +x\right)^{2}-n{\hbox{ (where }}x{\hbox{ is a small integer)}}}$

${\displaystyle y(x)\approx 2x\left\lceil {\sqrt {n}}\right\rceil }$

これは、 y が2 x [ √ n ]のオーダーであることを意味します。ただし、 y はxのnの平方根倍に比例して増加することも意味します。

滑らかさの可能性を高めるもう 1 つの方法は、単純に因数基数のサイズを大きくすることです。ただし、線形従属関係の存在を保証するには、因数基数内の素数の数よりも少なくとも 1 つの滑らかな関係を見つける必要があります。

たとえ何らかの関係y ( x ) が滑らかでなくても、2 つのyが因数基数の外側で同じ素数の積である場合、これらの部分関係のうち 2 つを結合して完全な関係を形成できる場合があります。[これは因数基数の拡張と同じであることに注意してください。] たとえば、因数基数が {2, 3, 5, 7} でn = 91 の場合、部分関係が存在します。

${\displaystyle {21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}}}$

${\displaystyle {29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}}}$

これらを掛け合わせます:

${\displaystyle {(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11^{2}{\pmod {91}}}}$

両辺に(11 ⁻¹ ) ²を91で割った余りを掛けます。11 ⁻¹を91で割った余りは58なので、次のようになります。

${\displaystyle (58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}$

${\displaystyle 14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}$

完全な関係を生成します。このような完全な関係（部分的な関係を組み合わせることによって得られる）は、サイクルと呼ばれます。2 つの部分的な関係からサイクルを形成すると、直接平方の合同につながることもありますが、まれです。

yの滑らかさをチェックする方法はいくつかあります。最も明白なのは試行分割ですが、データ収集フェーズの実行時間が長くなります。もう 1 つの方法として、ある程度受け入れられているのが楕円曲線法 (ECM) です。実際には、ふるい分けと呼ばれるプロセスが通常使用されます。f ( x ) が多項式である場合、次の式が成り立ちます 。 ${\displaystyle f(x)=x^{2}-n}$

${\displaystyle {\begin{aligned}f(x)&=x^{2}-n\\f(x+kp)&=(x+kp)^{2}-n\\&=x^{2}+2xkp+(kp)^{2}-n\\&=f(x)+2xkp+(kp)^{2}\equiv f(x){\pmod {p}}\end{aligned}}}$

したがって、f(x) ≡ 0 (mod p )をxについて解くと、 y = f ( x )となる一連の数y が生成され、それらはすべてpで割り切れます。これは、素数を法とする平方根を求めることで、Shanks-Tonelli アルゴリズムなどの効率的なアルゴリズムが存在します。 (これが二次ふるいの名前の由来です。y はxの二次多項式であり、ふるい分けのプロセスはエラトステネスのふるいのように機能します。)

ふるいは、まずバイトの大きな配列A [] のすべてのエントリをゼロに設定します。各pについて、 pを法として二次方程式を解いて 2 つの根αとβを取得し、次にy ( x ) = 0 mod pとなるすべてのエントリにlog( p ) の近似値を追加します。つまり、A [ kp  +  α ] とA [ kp  +  β ] です。因数ベースの素数の小さな累乗で割り切れる数を認識するには、 pの小さな累乗を法として二次方程式を解くことも必要です。

因数基数の終わりに、およそ log( x ² − n )のしきい値を超える値を含むA [] は、因数基数で分割されるy ( x )の値に対応します。 y ( x )を割り切る正確な素数に関する情報は失われていますが、小さな因数しかなく、小さな因数しか持たないことがわかっている数を因数分解するための優れたアルゴリズムが多数あります。たとえば、小さな素数による試し割り、SQUFOF、Pollard rho、ECM などです。これらは通常、何らかの組み合わせで使用されます。

機能するy ( x ) 値は多数あるため、最後の因数分解プロセスが完全に信頼できる必要はありません。多くの場合、プロセスは入力の 5% 程度で誤動作し、少量の追加ふるい分けが必要になります。

この例では、対数最適化や素数累乗を使わない標準的な二次ふるいを説明します。因数分解する数を N = 15347 とすると、Nの平方根の上限は124 になります。Nは小さいので、基本多項式y ( x ) = ( x + 124) ² − 15347 で十分です。

Nは小さいので、必要な素数は 4 つだけです。15347 がp を法として平方根をとる最初の 4 つの素数pは、2、17、23、29 です (言い換えると、15347 はこれらの素数のそれぞれを法として平方剰余になります)。これらの素数がふるい分けの基準になります。

ここで、 のふるいを構築し、基底の各素数に対してふるい分け処理を開始し、Y(X) の最初の 0 ≤ X < 100 をふるい分けすることを選択します。 ${\displaystyle V_{X}}$${\displaystyle Y(X)=(X+\lceil {\sqrt {N}}\rceil )^{2}-N=(X+124)^{2}-15347}$

${\displaystyle {\begin{aligned}V&={\begin{bmatrix}Y(0)&Y(1)&Y(2)&Y(3)&Y(4)&Y(5)&\cdots &Y(99)\end{bmatrix}}\\&={\begin{bmatrix}29&278&529&782&1037&1294&\cdots &34382\end{bmatrix}}\end{aligned}}}$

次のステップはふるい分けです。因数基底の各pについて、次の式を解きます。 ${\displaystyle \lbrace 2,17,23,29\rbrace }$

${\displaystyle Y(X)\equiv (X+\lceil {\sqrt {N}}\rceil )^{2}-N\equiv 0{\pmod {p}}}$

配列V内でpで割り切れる要素を見つけます。

解決するには、解決方法を入手してください。 ${\displaystyle p=2}$${\displaystyle (X+124)^{2}-15347\equiv 0{\pmod {2}}}$${\displaystyle X\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}}$

したがって、X=1から始めて2ずつ増やしていくと、各要素は2で割り切れる。これらの要素をそれぞれ2で割ると、

${\displaystyle V={\begin{bmatrix}29&139&529&391&1037&647&\cdots &17191\end{bmatrix}}}$

同様に、方程式の残りの素数pについても解きます。p > 2 の場合、モジュラー平方根が 2 つあるため、結果として得られる線形方程式は 2 つになることに注意してください。 ${\displaystyle \lbrace 17,23,29\rbrace }$${\displaystyle X\equiv {\sqrt {15347}}-124{\pmod {p}}}$

${\displaystyle {\begin{aligned}X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 3{\pmod {17}}\\&&\equiv 9-124&\equiv 4{\pmod {17}}\\X&\equiv {\sqrt {15347}}-124&\equiv 11-124&\equiv 2{\pmod {23}}\\&&\equiv 12-124&\equiv 3{\pmod {23}}\\X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 0{\pmod {29}}\\&&\equiv 21-124&\equiv 13{\pmod {29}}\\\end{aligned}}}$

各方程式は、x = aおよびそれを超える各p番目の値でpで割り切れることになります。基底の各素数について、 a、a + p、a +2 p、a +3 pなどでV をpで割ると、一意の素数 (1 乗) の積である滑らかな数が見つかります。 ${\displaystyle X\equiv a{\pmod {p}}}$${\displaystyle V_{x}}$

${\displaystyle V={\begin{bmatrix}1&139&23&1&61&647&\cdots &17191\end{bmatrix}}}$

Vの 1 に等しい要素はすべて滑らかな数に対応します。、、およびは1 に等しいため、これは次の式に対応します。 ${\displaystyle V_{0}}$${\displaystyle V_{3}}$${\displaystyle V_{71}}$

滑らかな数Y は性質 で発見されたので、アルゴリズムの残りの部分はDixon の因数分解法の他のバリエーションと同等になります。 ${\displaystyle Y\equiv Z^{2}{\pmod {N}}}$

方程式のサブセットの積の指数を書く

${\displaystyle {\begin{aligned}29&=2^{0}\cdot 17^{0}\cdot 23^{0}\cdot 29^{1}\\782&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{0}\\22678&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{1}\\\end{aligned}}}$

行列として次のように表される: ${\displaystyle {\pmod {2}}}$

${\displaystyle S\cdot {\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&1&1&1\end{bmatrix}}\equiv {\begin{bmatrix}0&0&0&0\end{bmatrix}}{\pmod {2}}}$

方程式の解は左零空間で与えられ、単純に

${\displaystyle S={\begin{bmatrix}1&1&1\end{bmatrix}}}$

したがって、3 つの方程式すべてを積ぶと、平方 (mod N) になります。

${\displaystyle 29\cdot 782\cdot 22678=22678^{2}}$

そして

${\displaystyle 124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2}}$

そこでアルゴリズムは

${\displaystyle 22678^{2}\equiv 3070860^{2}{\pmod {15347}}}$

結果をテストすると、GCD(3070860 - 22678, 15347) = 103 となり、これは 15347 の重要な因数であり、もう 1 つは 149 です。

このデモンストレーションは、2 次ふるいがnが大きい場合にのみ適切であることを示すのにも役立ちます。15347 のような小さな数の場合、このアルゴリズムは過剰です。試し割りやポラード ローを使えば、はるかに少ない計算で因数を見つけることができたでしょう。

実際には、 yにはさまざまな多項式が使用されるため、y ( x ) が大きくなり、滑らかなyの密度が悪くなると、この成長は多項式を切り替えることでリセットできます。通常どおり、 y ( x ) をn を法とする平方数として選択しますが、今度は次の形式になります 。

$${\displaystyle y(x)=(Ax+B)^{2}-n\qquad A,B\in \mathbb {Z} .}$$

${\displaystyle B}$が となるように選ばれるので、ある に対してとなります。多項式 y(x) は と書くことができます。Aが平方数または滑らかな数である場合、滑らかさを確認する必要があるのは因数だけです。 ${\displaystyle B^{2}=n{\pmod {A}}}$${\displaystyle B^{2}-n=AC}$${\displaystyle C}$${\displaystyle y(x)=A\cdot (Ax^{2}+2Bx+C)}$${\displaystyle (Ax^{2}+2Bx+C)}$

このアプローチは多重多項式二次ふるい (MPQS) と呼ばれ、因数分解に関与する各プロセッサにn 、因数基数、および多項式の集合を与えることができ、多項式によるふるい分けが完了するまで中央プロセッサと通信する必要がないため、並列化に最適です。

A未満のすべての因数で割った後、残りの数の部分 (余因子) がA ²未満である場合、この余因子は素数でなければなりません。実際には、関係のリストを余因子の順に並べ替えることで、この余因子を因数ベースに追加できます。y(a) = 7*11*23*137 および y(b) = 3*5*7*137 の場合、y(a)y(b) = 3*5*11*23 * 7 ² * 137 ²です。これは、完全な因数分解が実行される、ふるい分け配列のエントリのしきい値を下げることによって機能します。

しきい値をさらに下げ、y(x) 値を比較的大きな素数の積に因数分解する効果的なプロセス (ECM はこれに最適です) を使用すると、因数基数のほとんどの因数を持つ関係を見つけることができますが、2 つまたは 3 つのより大きな素数を持つ関係も見つけることができます。サイクル検索により、複数の素数を共有する一連の関係を 1 つの関係に組み合わせることができます。

多重多項式や大きな素数の最適化を含む実際の実装での現実的な例の一般的なパラメータ選択を示すために、ツール msieve を 267 ビットの半素数で実行し、次のパラメータを生成しました。

• 因数分解の試行カットオフ: 27 ビット
• ふるい間隔（多項式あたり）：393216（サイズ32768のブロック12個）
• 滑らかさの限界: 1300967 (50294 素数)
• 多項式Aの係数の因数の数: 10 (上記の多重多項式を参照)
• 大きな素数の境界: 128795733 (26 ビット) (上記の大きな素数を参照)
• 見つかった滑らかな値: 直接ふるいにかけて 25952、大きな素数で数字を組み合わせると 24462
• 最終的なマトリックスサイズ: 50294 × 50414、フィルタリングにより 35750 × 35862 に縮小
• 重要な依存関係が見つかりました: 15
• 合計時間（1.6 GHz UltraSPARC III の場合）: 35 分 39 秒
• 最大使用メモリ: 8 MB

数体ふるい(NFS)が発見されるまで、QS は漸近的に最も高速な既知の汎用因数分解アルゴリズムでした。現在、Lenstra 楕円曲線因数分解は、 QS と同じ漸近的な実行時間を持ちます ( nに同じサイズの素因数が 2 つある場合)。ただし、実際には、楕円曲線法で使用される多精度演算ではなく単精度演算を使用するため、QS の方が高速です。

1994 年 4 月 2 日、QS を使用してRSA-129の因数分解が完了しました。これは 129 桁の数字で、64 桁と 65 桁の 2 つの大きな素数の積です。この因数分解の因数基数は 524339 個でした。データ収集フェーズは、インターネットを介して分散方式で行われ、5000 MIPS 年かかりました。収集されたデータの合計は 2 GBでした。データ処理フェーズは、Bellcore (現在のTelcordia Technologies )のMasPar (超並列) スーパーコンピュータで 45 時間かかりました。これは、 1996 年 4 月 10 日に NFS を使用してRSA-130 の因数分解が完了するまで、汎用アルゴリズムによる最大の公開因数分解でした。それ以降に因数分解されたすべてのRSA 番号は、NFS を使用して因数分解されています。

現在のQS因数分解記録は140桁（463ビット）のRSA-140であり、2020年6月にパトリック・コンソールが6日間で約6,000コア時間を使って因数分解しました。^[3]

• PPMPQS と PPSIQS
• mpqs
• SIMPQS Archived 2020-05-06 at the Wayback Machineは、William Hart が書いた自己初期化多重多項式二次ふるいの高速実装です。大きな素数バリアントをサポートし、線形代数段階で Jason Papadopoulos のブロック Lanczos実装を使用します。SIMPQS は、 SageMathコンピュータ代数パッケージの qsieve コマンドとしてアクセス可能で、 Fast Library for Number Theoryの一部であり、ソース形式でダウンロードすることもできます。SIMPQS は、Athlon および Opteron マシンでの使用に最適化されていますが、一般的な 32 ビットおよび 64 ビット アーキテクチャのほとんどで動作します。すべて C で書かれています。
• Dario Alpern による因数分解アプレット。特定の条件が満たされた場合に二次ふるいを使用します。
• PARI /GPコンピュータ代数パッケージには、大きな素数変種を実装する自己初期化多重多項式二次ふるいの実装が含まれています。これは、Thomas Papanikolaou と Xavier Roblot によって LiDIA プロジェクト用に作成されたふるいから採用されました。自己初期化スキームは、Thomas Sosnowski の論文のアイデアに基づいています。
• 二次ふるいの変種は、MAGMAコンピュータ代数パッケージで利用できます。これは、1995 年の Arjen Lenstra の実装に基づいており、彼の「電子メールによる因数分解」プログラムで使用されています。
• msieve は、Jason Papadopoulos によって書かれた、単一および二重の大きな素数をサポートする多重多項式二次ふるいの実装です。ソース コードと Windows バイナリが利用可能です。
• Ben Buhrow が作成した YAFU は、おそらく利用可能な二次ふるいの実装の中で最速です。たとえば、RSA-100 は、2.5 GHz Xeon 6248 CPU の 4 つのコアで 15 分未満で分解されました。すべての重要なサブルーチンは、 AMD または Intel プロセッサのAVX2またはAVX-512 SIMD命令を使用します。これは、Jason Papadopoulos のブロック Lanczos コードを使用します。Windows および Linux 用のソース コードとバイナリが利用可能です。
• Ariel は、教育目的の二次ふるいのシンプルな Java 実装です。
• java-math-library には、おそらく Java で書かれた最も高速な二次ふるい (PSIQS 4.0 の後継) が含まれています。
• Java QS は、QS の基本実装を含むオープンソースの Java プロジェクトです。2016 年 2 月 4 日に Ilya Gazman によってリリースされました。
• C Quadratic Sieve は、自己初期化 Quadratic Sieve の実装を含む、完全に C で記述された因数分解器です。このプロジェクトは、William Hart の FLINT 因数分解器に触発されています。2022 年に Michel Leonard によってリリースされたソースは、外部ライブラリに依存せず、1 分で 240 ビットの数値を因数分解し、2 時間で 300 ビットの数値を因数分解できます。
• Joseph Wood による RcppBigIntAlgos パッケージは、 R プログラミング言語用の多重多項式二次ふるいの効率的な実装を提供します。これは C++ で書かれており、100 桁の半素数を楽に因数分解できます。たとえば、300 ビットの半素数 (91 桁) は 1 時間で因数分解され、RSA-100 はApple M2 プロセッサを搭載した MacBook Air で 10 時間以内に因数分解されました。

Wikiversityには、二次ふるいに関する学習リソースがあります。

• レンストラ楕円曲線因数分解
• 素数判定テスト

• 参考論文「二次ふるい分解アルゴリズム」、Eric Landquist 著