レンストラ楕円曲線因数分解

レンストラ楕円曲線因数分解または楕円曲線因数分解法( ECM ) は、楕円曲線を使用する高速で指数関数的実行時間の短い整数因数分解アルゴリズムです。汎用因数分解の場合、ECM は 3 番目に高速な因数分解法として知られています。2 番目に高速なのは多重多項式二次ふるいで、最も高速なのは一般数体ふるいです。レンストラ楕円曲線因数分解は、ヘンドリック レンストラにちなんで名付けられました。

実際には、ECM は小さな因数を見つけるのに最適であるため、特殊用途の因数分解アルゴリズムと見なされています。現在のところ、50 ～ 60桁を超えない約数^{[アップデート]}に最適なアルゴリズムです。これは、その実行時間が、因数分解する数nのサイズではなく、最小の因数pのサイズによって左右されるためです。ECM は、多くの因数を持つ非常に大きな整数から小さな因数を取り除くためによく使用されます。残った整数がまだ合成数である場合、その因数には大きな因数しかなく、汎用的な手法を使用して因数分解されます。これまでに ECM を使用して見つかった最大の因数は、小数点以下 83 桁で、2013 年 9 月 7 日に R. Propper によって発見されました。^[1]テストする曲線の数を増やすと因数を見つける可能性が高くなりますが、桁数の増加に対して 直線的ではありません。

与えられた自然数の因数を見つけるための Lenstra 楕円曲線因数分解法は、次のように機能します。 ${\displaystyle n}$

1. 上のランダムな楕円曲線( を法とする整数)を選び、その上に非自明な点を伴う形式の方程式を持ちます。 ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle n}$${\displaystyle y^{2}=x^{3}+ax+b{\pmod {n}}}$ ${\displaystyle P(x_{0},y_{0})}$

   これは、最初にランダムを選択し、次にポイントが曲線上にあることを確認するように設定することで実行できます。${\displaystyle x_{0},y_{0},a\in \mathbb {Z} /n\mathbb {Z} }$${\displaystyle b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n}}}$

2. 曲線上の 2 つの点の加算を定義して、グループを定義できます。加法則は楕円曲線に関する記事に記載されています。

   点の倍数を繰り返すことができます: 。加法の公式には、とを結合する弦のモジュラー勾配の取得、および を法とする剰余類間の除算が含まれ、これは拡張ユークリッド互除法を使用して実行されます。特に、 による除算にはの計算が含まれます。${\displaystyle P}$${\displaystyle [k]P=P+\ldots +P{\text{ (k 回)}}}$${\displaystyle P}$${\displaystyle Q}$${\displaystyle n}$${\displaystyle v{\bmod {n}}}$${\displaystyle \gcd(v,n)}$

   の形式の傾きを で計算すると仮定すると、 の場合、点の追加の結果は になります。これは、と曲線を結合する「垂直」な直線の交点に対応する「無限遠」の点です。ただし、の場合、点の追加によって曲線上に意味のある点は生成されません。さらに重要なのは、が の重要な因数であるということです。${\displaystyle u/v}$${\displaystyle \gcd(u,v)=1}$${\displaystyle v=0{\bmod {n}}}$${\displaystyle \infty}$${\displaystyle P(x,y),P'(x,-y)}$${\displaystyle \gcd(v,n)\neq 1,n}$${\displaystyle \gcd(v,n)}$${\displaystyle n}$

3. 楕円曲線 ( )上で計算します。ここで は多数の小さな数の積、つまりp-1 アルゴリズムのように小さな素数を小さな累乗した積、またはあまり大きくないの階乗です。これは、一度に 1 つの小さな因数を計算することで効率的に実行できます。たとえば、 を取得するには、最初にを計算し、次にを計算し、次に を計算し、というように計算します。は、ごとの点の加算が妥当な時間で実行できる ように、十分に小さくなるように選択されます。${\displaystyle [k]P}$${\displaystyle {\bmod {n}}}$${\displaystyle k}$ ${\displaystyle B!}$${\displaystyle B}$${\displaystyle [B!]P}$${\displaystyle [2]P}$${\displaystyle [3]([2]P)}$${\displaystyle [4]([3!]P)}$${\displaystyle B}$${\displaystyle B}$
   • 上記の計算をすべて完了しても逆元 ( ) に遭遇しない場合は、楕円曲線 (素数を法とする) の順序が十分に滑らかではないことを意味するため、別の曲線と開始点を使用して再試行する必要があります。${\displaystyle {\bmod {n}}}$
   • に遭遇したら、それで終わりです。それは の非自明な因数です。${\displaystyle \gcd(v,n)\neq 1,n}$${\displaystyle n}$

計算時間の複雑さは、その数値の最小の素因数の大きさに依存し、exp[( √2  +  o (1)) √lnplnlnp ]で表す  こと ができます。ここで、pはnの最小の因数、またはL表記ではです。 ${\displaystyle L_{p}\left[{\frac {1}{2}},{\sqrt {2}}\right]}$

pとq がnの 2 つの素因数である場合、y ²  =  x ³  + ax  +  b  (mod  n )は、 pを法として 、qを法 としても同じ式を意味します。 -加算を含むこれら 2 つの小さな楕円曲線は、真のグループになります。これらのグループがそれぞれN _pとN _{q の}要素を持つ場合、元の曲線上の任意の点Pについて、ラグランジュの定理により、k  > 0は最小であり、曲線上でp を法とすると、 k がN _{p を}割り切ることを意味します。さらに、。同様のステートメントがqを法とする曲線にも当てはまります。楕円曲線がランダムに選択される場合、N _pとN _{q はそれぞれ}p  + 1とq  + 1に近い乱数です​​ (以下を参照)。したがって、 N _pとN _qのほとんどの素因数が同じである可能性は低く、ePの計算中に、 pを法として無限大だが q を法として無限大ではない kP 、または その逆の kPに遭遇する可能性がかなりあります。 この場合、kP は元の曲線上に存在せず、計算では、gcd( v、p ) =  pまたはgcd( v、  q ) =  qのいずれかであるv が見つかりましたが、両方ではありません。 つまり、gcd( v、  n )はnの 非自明な因数を与えました。${\displaystyle \boxplus}$${\displaystyle kP=\infty }$${\displaystyle N_{p}P=\infty }$

ECM は本質的には、古いp  − 1アルゴリズムの改良版です。p  − 1アルゴリズムは、 bの値が小さい場合にp  − 1がb べき乗滑らかとなるような素因数p を見つけます。p  − 1の倍数である任意のeと、 pと互いに素である任意のaについて、フェルマーの小定理により、 a ^e  ≡ 1 ( mod p )が成り立ちます。すると、gcd ( a ^e  − 1,  n )はnの因数を生成する可能性が高くなります。ただし、 p  - 1 に大きな素因数がある場合、たとえば強い素数を含む数の場合、アルゴリズムは失敗します。

ECM は、常に位数p  − 1を持つ Z _pの乗法群を考慮するのではなく、有限体Z _p上のランダム楕円曲線の群を考慮することでこの障害を回避します。

Z _p上の楕円曲線の群の位数は、ハッセの定理により、p  + 1 − 2 √ pとp  + 1 + 2 √ pの間で（かなりランダムに）変化し、いくつかの楕円曲線では滑らかになる可能性があります。ハッセ区間で滑らかな群位数が見つかるという証明はありませんが、発見的確率的方法、適切に最適化されたパラメータ選択によるキャンフィールド・エルデシュ・ポメランスの定理、およびL 表記を使用することで、滑らかな群位数を得るまでにL [ √ 2 /2, √ 2 ]曲線を試すことが期待できます。この発見的推定は、実際には非常に信頼性があります。

以下の例は、Trappe & Washington (2006) からの抜粋ですが、詳細がいくつか追加されています。

n = 455839を因数分解します。楕円曲線y ² = x ³ + 5 x – 5を選択し、その上の点P = (1, 1)を選択して、 (10!) Pを計算してみましょう。

ある点A =( x , y )における接線の傾きは、 s = (3 x ² + 5)/(2 y ) (mod n)です。s を使用して 2 Aを計算できます。 sの値がa/b の形式 ( b > 1かつgcd( a , b ) = 1) である場合、 bのモジュラー逆数を見つける必要があります。それが存在しない場合、 gcd( n , b ) はnの非自明な因数です。

まず2 Pを計算します。s ( P ) = s (1,1) = 4 なので、2 P = ( x ′ , y ′ )の座標はx ′ = s ² – 2 x = 14、y ′ = s ( x – x ′ ) – y = 4(1 – 14) – 1 = –53となり、すべての数値は理解されています(mod n )。この 2 P が実際に曲線上にあることを確認すると、 (–53) ² = 2809 = 14 ³ + 5·14 – 5 となります。

次に3(2 P )を計算します。s (2 P ) = s (14,-53) = –593/106 (mod n )となります。ユークリッドの互除法を使用すると、455839 = 4300·106 + 39、106 = 2·39 + 28、39 = 28 + 11、28 = 2·11 + 6、11 = 6 + 5、6 = 5 + 1となります。したがって、gcd(455839, 106) = 1 となり、逆順に解くと (拡張ユークリッドの互除法のバージョン)、1 = 6 – 5 = 2·6 – 11 = 2·28 – 5·11 = 7·28 – 5·39 = 7·106 – 19·39 = 81707·106 – 19·455839 となります。したがって、106 ⁻¹ = 81707 (mod 455839)、および–593/106 = –133317 (mod 455839) です。このsが与えられれば、上記と同じように2(2 P )の座標を計算できます。4 P = (259851, 116255)。これが実際に曲線上の点であることを確認するために、y ² = 54514 = x ³ + 5 x – 5 (mod 455839) です。この後、 を計算できます。 ${\displaystyle 3(2P)=4P\boxplus 2P}$

同様に 4! Pなども計算できますが、8! P の場合は 599を逆数(mod 455839) する必要があります。ユークリッドの互除法によれば、455839 は 599 で割り切れるので、因数分解 455839 = 599·761 が見つかりました。

これがうまくいった理由は、曲線(mod 599)には640 = 2 ⁷ ·5点があるのに対し、曲線(mod 761)には777 = 3 · 7 · 37点があるためです。さらに、640 と 777 は、それぞれ曲線(mod 599)と(mod 761)上でkP = ∞となる最小の正の整数kです。8 !は 640 の倍数ですが 777 の倍数ではないため、曲線(mod 599)上では8! P = ∞となりますが、曲線 (mod 761) 上では 8! P = ∞ となりません。そのため、ここで繰り返し加算が破綻し、因数分解が行われます。

上の射影平面を考える前に、まず上の「通常の」射影空間を考えます。点の代わりに、原点を通る線を考えます。線は、≡ ∃ c ≠ 0で与えられる同値関係 ~ の下で、ゼロでない点 として表すことができます。この場合、x' = c x、y' = c y、z' = c zとなります。この同値関係の下では、空間は射影平面と呼ばれます。 で示される点は、3 次元空間で原点を通る線に対応します。任意の方向に線を引くには、少なくとも x'、y'、または z' ≠ 0 のいずれか 1 つが必要であるため、この空間には点が存在しないことに注意してください。ここで、ほとんどすべての線が ( X、Y 、 1) 平面などの任意の参照平面を通過する一方で、座標 ( X 、 Y 、 0 )を持つこの平面に正確に平行な線は、その上にあるアフィン ( X 、 Y ) 平面で使用される「無限遠点」として一意に方向を指定することに注意してください。 ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )/\sim ,}$${\displaystyle \mathbb {R} }$${\displaystyle (x,y,z)}$${\displaystyle (x,y,z)\sim (x',y',z')}$ ${\displaystyle \mathbb {P} ^{2}}$${\displaystyle (x:y:z)}$${\displaystyle (0:0:0)}$

アルゴリズムでは、体 上の楕円曲線の群構造のみが使用されます。体 は必ずしも必要ではないため、有限体も楕円曲線上の群構造を提供します。ただし、同じ曲線と、素数でないnでの上の演算を考慮しても群は得られません。楕円曲線法は、加法則の失敗例を利用します。 ${\displaystyle \mathbb {R} }$${\displaystyle \mathbb {R} }$${\displaystyle (\mathbb {Z} /n\mathbb {Z} )/\sim }$

ここで、アルゴリズムを射影座標で述べます。中立要素は無限遠点によって与えられます。nを(正の) 整数とし、楕円曲線 (何らかの構造を持つ点の集合) を考えます。 ${\displaystyle (0:1:0)}$${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )=\{(x:y:z)\in \mathbb {P} ^{2}\ |\ y^{2}z=x ^{3}+axz^{2}+bz^{3}\}}$

1. ≠ 0 のものを選択してください。${\displaystyle x_{P},y_{P},a\in \mathbb {Z} /n\mathbb {Z} }$
2. を計算します。楕円曲線Eはワイエルシュトラス形式では で与えられ、射影座標を使用すると、楕円曲線は同次方程式 で与えられます。その点は です。${\displaystyle b=y_{P}^{2}-x_{P}^{3}-ax_{P}}$${\displaystyle y^{2}=x^{3}+ax+b}$${\displaystyle ZY^{2}=X^{3}+aZ^{2}X+bZ^{3}}$${\displaystyle P=(x_{P}:y_{P}:1)}$
3. この楕円曲線の上限を選択します。注:楕円曲線Eの( で示される)上の群の順序がB 滑らかなの場合にのみ因数p が見つかります。つまり、 のすべての素因数はB以下でなければなりません。${\displaystyle B\in \mathbb {Z} }$${\displaystyle \mathbb {Z} /p\mathbb {Z} }$${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$
4. 計算します。${\displaystyle k={\rm {lcm}}(1,\dots ,B)}$
5. 環 で( k回)を計算します。 がB滑らかでnが素数 (したがって が体)の場合、 となることに注意してください。ただし、 nの何らかの約数pに対してのみがB 滑らかな場合、 nが素数でない場合は加算と乗算が明確に定義されないため、積は (0:1:0) にならない可能性があります。この場合、非自明な約数が見つかることがあります。${\displaystyle kP:=P+P+\cdots +P}$${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )}$${\displaystyle \#E(\mathbb {Z} /n\mathbb {Z} )}$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle kP=(0:1:0)}$${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$
6. そうでない場合は、ステップ2に戻ります。これが発生した場合は、製品を簡素化するときにこれに気付くでしょう。${\displaystyle kP.}$

ポイント 5 では、適切な状況下では非自明な除数が見つかる可能性があると述べられています。Lenstra の記事 (楕円曲線による整数の因数分解) で指摘されているように、加算には という仮定が必要です。がと で異なる場合 (それ以外の場合、加算は同様に機能しますが、少し異なります)、加算は次のように機能します。 ${\displaystyle \gcd(x_{1}-x_{2},n)=1}$${\displaystyle P,Q}$${\displaystyle (0:1:0)}$

• 計算するには：、${\displaystyle R=P+Q;}$ ${\displaystyle P=(x_{1}:y_{1}:1),Q=(x_{2}:y_{2}:1)}$
• ${\displaystyle \lambda =(y_{1}-y_{2})(x_{1}-x_{2})^{-1}}$、
• ${\displaystyle x_{3}=\lambda ^{2}-x_{1}-x_{2}}$、
• ${\displaystyle y_{3}=\lambda (x_{1}-x_{3})-y_{1}}$、
• ${\displaystyle R=P+Q=(x_{3}:y_{3}:1)}$。

加算が失敗した場合、これは計算の失敗によるものです。特に、nが素数でない場合 (つまり、体でない場合)は必ずしも計算できないためです。体であることを利用せずに、次のように計算できます。 ${\displaystyle \lambda .}$${\displaystyle (x_{1}-x_{2})^{-1}}$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

• ${\displaystyle \lambda '=y_{1}-y_{2}}$、
• ${\displaystyle x_{3}'={\lambda '}^{2}-x_{1}(x_{1}-x_{2})^{2}-x_{2}(x_{1}-x_{2})^{2}}$、
• ${\displaystyle y_{3}'=\lambda '(x_{1}(x_{1}-x_{2})^{2}-x_{3}')-y_{1}(x_{1}-x_{2})^{3}}$、
• ${\displaystyle R=P+Q=(x_{3}'(x_{1}-x_{2}):y_{3}':(x_{1}-x_{2})^{3})}$可能であれば簡素化します。

この計算は常に正当であり、 Z座標の gcd がn ≠ (1 またはn ) の場合、簡略化が失敗すると、 nの非自明な約数が見つかります。

エドワーズ曲線を使用すると、モンゴメリ曲線やワイエルシュトラス曲線(他の方法)を使用する場合よりも、モジュラー乗算が少なくなり、時間も短縮されます。エドワーズ曲線を使用すると、より多くの素数を見つけることもできます。

定義。を となる体とし、 となるとします。このとき、ねじれ Edwards 曲線は次のように与えられます。 Edwards 曲線は、 となるねじれ Edwards 曲線です。 ${\displaystyle k}$${\displaystyle 2\neq 0}$${\displaystyle a,d\in k\setminus \{0\}}$${\displaystyle a\neq d}$${\displaystyle E_{E,a,d}}$${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}.}$${\displaystyle a=1}$

エドワーズ曲線上の点の集合を構築する方法としては、アフィン点の集合、射影点の集合、反転点の集合、拡張点の集合、および完成点の集合の 5 つが知られています。

アフィン点の集合は次のように与えられます。

${\displaystyle \{(x,y)\in \mathbb {A} ^{2}:ax^{2}+y^{2}=1+dx^{2}y^{2}\}}$。

加法則は次のように与えられる。

${\displaystyle (e,f),(g,h)\mapsto \left({\frac {eh+fg}{1+degfh}},{\frac {fh-aeg}{1-degfh}}\right).}$

点(0,1)はその中立要素であり、 の逆関数はです。 ${\displaystyle (e,f)}$${\displaystyle (-e,f)}$

他の表現は、射影ワイエルシュトラス曲線がアフィン曲線からどのように導かれるかと同様に定義されます。

エドワーズ形式の任意の楕円曲線は位数 4 の点を持ちます。したがって、上のエドワーズ曲線の捩れ群はまたは と同型です。 ${\displaystyle \mathbb {Q} }$${\displaystyle \mathbb {Z} /4\mathbb {Z} ,\mathbb {Z} /8\mathbb {Z} ,\mathbb {Z} /12\mathbb {Z} ,\mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z} }$${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$

ECM の最も興味深いケースはとです。これらは、素数を法とする曲線の群の順序がそれぞれ 12 と 16 で割り切れるように強制するからです。次の曲線は と同型の捩れ群を持ちます。 ${\displaystyle \mathbb {Z} /12\mathbb {Z} }$${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$${\displaystyle \mathbb {Z} /12\mathbb {Z} }$

• ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$点と​${\displaystyle (a,b)}$${\displaystyle b\notin \{-2,-1/2,0,\pm 1\},a^{2}=-(b^{2}+2b)}$${\displaystyle d=-(2b+1)/(a^{2}b^{2})}$
• ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$点と​${\displaystyle (a,b)}$${\displaystyle a={\frac {u^{2}-1}{u^{2}+1}},b=-{\frac {(u-1)^{2}}{u^{2}+1}}}$${\displaystyle d={\frac {(u^{2}+1)^{3}(u^{2}-4u+1)}{(u-1)^{6}(u+1)^{2}}},u\notin \{0,\pm 1\}.}$

3の位数を持つすべてのエドワーズ曲線は、上記の方法で記述できます。 および と同型のねじれ群を持つ曲線は、素数を見つけるのに効率的である可能性があります。^[2]${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z} }$

上記の文章は、楕円曲線因数分解の第一段階に関するものです。ここでは、の中立元となるような素因数p を見つけることが期待されます。第二段階では、において小さな素数位数となるような素因数qを見つけることが期待されます。 ${\displaystyle sP}$${\displaystyle E(\mathbb {Z} /p\mathbb {Z} )}$${\displaystyle sP}$${\displaystyle E(\mathbb {Z} /q\mathbb {Z} )}$

順序がと の間であることを期待します。ここで、 はステージ 1 で決定され、 はステージ 2 の新しいパラメータです。 の小さい順序を確認するには、各素数lに対してn を法として計算します。 ${\displaystyle B_{1}}$${\displaystyle B_{2}}$${\displaystyle B_{1}}$${\displaystyle B_{2}}$${\displaystyle sP}$${\displaystyle (ls)P}$

^{Bernsteinら[2]}は、ツイストエドワーズ楕円曲線やその他の技術を使用して、ECMの最適化された実装を提供しました。唯一の欠点は、より汎用的な実装であるZimmermanのGMP-ECMよりも小さい合成数で動作することです。

超楕円曲線を使用して整数を因数分解する最近の開発があります。Cosset は、彼の論文 (2010 年) で、種数 2 の超楕円曲線 (つまり、次数 5 のfを持つ曲線) を構築できることを示しており、これは 2 つの「通常の」楕円曲線を同時に使用した場合と同じ結果をもたらします。Kummer 面を使用することで、計算がより効率的になります。超楕円曲線 (楕円曲線と比較した場合) の欠点は、この代替計算方法によって補われます。したがって、Cosset は、因数分解に超楕円曲線を使用することは、楕円曲線を使用することよりも悪くない、と大まかに主張しています。 ${\displaystyle y^{2}=f(x)}$

バーンスタイン、ヘニンガー、ルー、ヴァレンタは、エドワーズ曲線を使用したECMの量子バージョンであるGEECMを提案しています。^[3]これは、十分な数の量子ビットを持ち、EECMを実行する古典的なコンピュータと同等の速度を持つ量子コンピュータを想定して、グローバーのアルゴリズムを使用して、標準的なEECMと比較して見つかった素数の長さを約2倍にします。

• バーンスタイン、ダニエル・J.バークナー、ピーター。タンジャ、ランゲ。ピーターズ、クリスティアーヌ (2013)。 「エドワーズ曲線を使用したECM」。計算の数学。82 (282): 1139–1179。土井：10.1090/S0025-5718-2012-02633-0。MR  3008853。
• ボスマ、W.ハルスト、MPM van der (1990)。円状切除術による初等性の証明。博士号アムステルダム大学の論文。OCLC  256778332。
• ブレント、リチャードP. (1999)。「 10番目のフェルマー数の因数分解」。計算数学。68 (225): 429–451。Bibcode :1999MaCom..68..429B。doi : 10.1090/ S0025-5718-99-00992-8。MR  1489968 。
• コーエン、ヘンリ（1993）。計算代数的数論コース。数学大学院テキスト。第138巻。ベルリン：シュプリンガー出版社。doi ： 10.1007 / 978-3-662-02945-9。ISBN 978-0-387-55640-6. MR  1228206. S2CID  118037646.
• Cosset, R. (2010). 「種数 2 の曲線による因数分解」.計算数学. 79 (270): 1191–1208. arXiv : 0905.2325 . Bibcode :2010MaCom..79.1191C. doi :10.1090/S0025-5718-09-02295-9. MR  2600562. S2CID  914296.
• Lenstra, AK ; Lenstra Jr., HW 編 (1993)。数体ふるいの開発。数学講義ノート。第 1554 巻。ベルリン: Springer-Verlag。doi : 10.1007/ BFb0091534。ISBN 978-3-540-57013-4MR  1321216 。
• Lenstra Jr., HW (1987). 「楕円曲線による整数の因数分解」(PDF) . Annals of Mathematics . 126 (3): 649–673. doi :10.2307/1971363. hdl : 1887/2140 . JSTOR  1971363. MR  0916721.
• ポメランス、カール、クランドール、リチャード (2005)。素数: 計算の観点(第 2 版)。ニューヨーク: シュプリンガー。ISBN 978-0-387-25282-7. MR  2156291。
• ポメランス、カール (1985)。「2 次ふるい分解アルゴリズム」。暗号学の進歩、Eurocrypt '84 会議録。コンピュータ サイエンスの講義ノート。第 209 巻。ベルリン: Springer-Verlag。pp. 169–182。doi : 10.1007 /3-540-39757-4_17。ISBN 978-3-540-16076-2. MR  0825590。
• ポメランス、カール (1996) 。「2つのふるいの物語」(PDF)。アメリカ数学会報。43 (12): 1473–1485。MR  1416721。
• Silverman, Robert D. (1987). 「多重多項式二次ふるい」.計算数学. 48 (177): 329–339. doi : 10.1090/S0025-5718-1987-0866119-8 . MR  0866119.
• Trappe, W.; Washington, LC (2006)。暗号理論入門（第2版）。サドルリバー、ニュージャージー：ピアソン・プレンティス・ホール。ISBN 978-0-13-186239-5. MR  2372272。
• サミュエル・S・ワグスタッフ・ジュニア(2013)。『因数分解の喜び』。プロビデンス、ロードアイランド州：アメリカ数学会。pp. 173–190。ISBN 978-1-4704-1048-3。
• Watras, Marcin (2008)。暗号、数値解析、および非常に大きな数。ビドゴシュチュ: Wojciechowski-Steinhagen。PL:5324564。

• 楕円曲線法を使用した因数分解。ECM を使用し、より高速な場合は自己初期化二次ふるいに切り替える WebAssembly アプリケーションです。
• GMP-ECM は、Wayback Machineで 2009-09-12 にアーカイブされてお​​り、ECM の効率的な実装です。
• ECMNet は、いくつかの因数分解プロジェクトで動作する簡単なクライアント サーバー実装です。
• pyecm、ECM の Python 実装。
• 分散コンピューティング プロジェクト yoyo@Home サブプロジェクト ECM は、さまざまな種類の数値の因数を見つけるために使用される楕円曲線因数分解のプログラムです。
• Lenstra 楕円曲線因数分解アルゴリズムのソース コード シンプルな C および GMP 楕円曲線因数分解アルゴリズムのソース コード。
• EECM-MPFQ MPFQ 有限体ライブラリで記述された Edwards 曲線を使用した ECM の実装。