楕円曲線素数性

数学において、楕円曲線素数性判定法、または楕円曲線素数性証明 (ECPP) は、素数性証明の中で最も迅速で広く使用されている方法の 1 つです。^[1]これは、1986 年にShafi Goldwasserと Joe Kilianによって提唱されたアイデアであり、同年にAOL Atkinによってアルゴリズムに変換されました。このアルゴリズムはその後数人の共同研究者によって変更および改良され、特に1993 年にはAtkin と François Morain  [de]によって改良されました。 ^[2]因数分解に楕円曲線 を使用するという概念は1985 年にHW Lenstraによって開発され、素数性判定 (および証明) での使用への影響がすぐに明らかになりました。

素数判定はフェルマーの時代から存在する分野である。フェルマーの時代は、ほとんどのアルゴリズムが因数分解に基づいていたが、これは大きな入力では扱いにくくなっていた。現代のアルゴリズムは、数が素数であるかどうかとその因数が何であるかを判定する問題を別々に扱う。これは、現代の暗号の出現によって実用上重要になった。現在の多くのテストは確率的な出力（ベイリー–PSW素数判定テストやミラー–ラビンテストのように、 Nが合成数であるか、おそらく素数であるかのいずれか）をもたらすが、楕円曲線テストは素数性（または合成数であること）を迅速に検証可能な証明書で証明する。^[3]

ポックリントン素数判定法など、これまで知られていた素数証明法では、が素数であることを証明するために、 を少なくとも部分的に因数分解する必要がありました。その結果、これらの方法はある程度の運を必要とし、実際には一般的に時間がかかります。 ${\displaystyle N\pm 1}$${\displaystyle N}$

これは汎用アルゴリズムであり、数が特殊な形式であるかどうかに依存しません。ECPP は現在、一般的な数の素数性をテストするための最速の既知のアルゴリズムですが、最悪の場合の実行時間は不明です。ECPP は時間内でヒューリスティックに実行されます。

${\displaystyle O((\log n)^{5+\varepsilon })\,}$

に対しては となる。^[4]この指数は、発見的議論によって、いくつかのバージョンでは まで減少することがある。ECPP は、他のほとんどの素数判定テストと同じように動作し、が素数となるようなグループを見つけて、そのサイズが となることを示す。ECPP の場合、グループは がグループ上で因数分解しやすい 二次形式の有限集合上の楕円曲線である。${\displaystyle \varepsilon >0}$${\displaystyle 4+\epsilon }$${\displaystyle p}$${\displaystyle p-1}$

ECPP は、再帰によってAtkin – Goldwasser –Kilian–Morain素数証明書を生成し、その証明書の検証を試みます。最もCPU時間を要するステップは証明書の生成です。これは、クラス フィールドの因数分解を実行する必要があるためです。証明書は迅速に検証できるため、動作のチェックにはほとんど時間がかかりません。

2023年5月現在^{[アップデート]}、ECPP法で証明された最大の素数はである。^{[5]この証明は、Andreas Enge氏が自身のfastECPPソフトウェア}CMを使用して行った。 ${\displaystyle 5^{104824}+104824^{5}}$

楕円曲線素数判定は、その判定のベースとなるポックリントン基準に類似した基準に基づいています。^{[6] [7]} ここで、群は に置き換えられ、Eは適切に選択された楕円曲線です。ここで、ポックリントン基準に類似し、楕円曲線素数判定のゴールドワッサー・キリアン・アトキン形式を生み出す、私たちの判定のベースとなる命題を述べます。 ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$${\displaystyle E(\mathbb {Z} /n\mathbb {Z} ),}$

N を正の整数、E を方程式で定義される集合とします。E上の通常の加法則を使用してE を考え、 E上の中立元を 0 と書きます。 ${\displaystyle y^{2}=x^{3}+ax+b{\bmod {N}}.}$${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$

mを整数とする。mを割り切る素数qがあり、qがより大きい場合、 E上の点Pが存在し、 ${\displaystyle \left({\sqrt[{4}]{N}}+1\right)^{2}}$

（１）mP = 0

（２）（ｍ／ｑ）Ｐは定義され、０と等しくない

するとNは素数になります。

Nが合成数であれば、 N を割り切る素数が存在する。 をEと同じ式で定義される楕円曲線として定義するが、 Nではなく p を法として評価する 。を群の位数として定義する。楕円曲線に関するハッセの定理により、 ${\displaystyle p\leq {\sqrt {N}}}$${\displaystyle E_{p}}$${\displaystyle m_{p}}$${\displaystyle E_{p}}$

${\displaystyle m_{p}\leq p+1+2{\sqrt {p}}=\left({\sqrt {p}}+1\right)^{2}\leq \left({\sqrt[{4}]{N}}+1\right)^{2}}$

そして、次のような性質を持つ 整数uが存在する。${\displaystyle \gcd(q,m_{p})=1}$

${\displaystyle uq\equiv 1{\bmod {m_{p}}}.}$

を点Pを法としてpを評価すると 、${\displaystyle P_{p}}$${\displaystyle E_{p}}$

${\displaystyle (m/q)P_{p}=uq(m/q)P_{p}=umP_{p}=0,}$

(1)によれば、はmPと同じ方法を用いて計算されるが、  N (および)を法としてではなく pを法として計算される。 ${\displaystyle mP_{p}}$${\displaystyle p\mid N}$

これは（２）と矛盾する。なぜなら、（ｍ／ｑ）Ｐが定義され、０（ｍｏｄ Ｎ ）と等しくない 場合、同じ方法を 法Ｎの代わりに 法ｐで計算すると次のようになるからである。^[8]

${\displaystyle (m/q)P_{p}\neq 0.}$

この命題から、整数Nが素数であることを証明するアルゴリズムを構築することができます。これは次のように行われます。^[6]

3つの整数a、x、yをランダムに選び、

${\displaystyle b\equiv y^{2}-x^{3}-ax{\pmod {N}}}$

ここで、P = ( x , y ) はE上の点であり、E はによって定義されます。次に、 E上の点の数を数えるアルゴリズムが必要です。Eに適用すると、このアルゴリズム (Koblitz らはSchoof のアルゴリズムを提案) は、 Nが素数である場合に、曲線E上のF _N上の点の数である数m を生成します。点を数えるアルゴリズムが未定義の式で停止した場合、これによってNの非自明な因数を決定できます。成功した場合、曲線Eが許容可能かどうかを判断するための基準を適用します。 ${\displaystyle y^{2}=x^{3}+ax+b}$

m を、 が小さな整数でq が大きな確率的素数（たとえば、確率的素数判定に合格する数）の形式で記述できる場合、 E を破棄しません。それ以外の場合は、曲線を破棄し、別の 3 つ組（a、x、y）をランダムに選択して最初からやり直します。ここでの考え方は、大きな素数qで割り切れるm を見つけることです。この素数はm（またはN）より数桁小さいため、 q が素数であることはNよりも簡単に証明できます。 ${\displaystyle m=kq}$${\displaystyle k\geq 2}$

基準を満たす曲線が見つかったと仮定して、mPとkP の計算に進みます。 2 つの計算のいずれかが未定義の式を生成する場合、Nの重要な因数を得ることができます。 両方の計算が成功した場合は、結果を調べます。

Nが素数でないことは明らかです。なぜなら、 Nが素数であれば、Eの位数はmとなり、Eのどの要素もmを掛けると 0 になるからです。kP = 0 の場合、アルゴリズムはE を破棄し、別のa、x、yの組み合わせでやり直します。 ${\displaystyle mP\neq 0}$

さて、 の場合、の前の命題からNは素数であることがわかります。しかし、qの素数性という問題が 1 つあります。これは同じアルゴリズムを使用して検証されます。そこで、 Nの素数性がqの素数性、およびより小さな「可能性のある素数」に依存し、あるしきい値に達するとq が非再帰的決定論的アルゴリズムを適用できるほど十分に小さいと見なされるという再帰アルゴリズムを説明しました。^{[9] [10]}${\displaystyle mP=0}$${\displaystyle kP\neq 0}$

アトキンとモレインは、「GKの問題は、シューフのアルゴリズムは実装がほぼ不可能と思われることだ」と述べています。^{[3]ゴールドワッサー-キリアンアルゴリズムの推奨アルゴリズムであるシューフのアルゴリズムを使用して}E 上のすべての点を数えるのは非常に時間がかかり、面倒です。しかし、シューフによる元のアルゴリズムは、短時間で点の数を提供するのに十分効率的ではありません。^[11]これらのコメントは、エルキーズとアトキンがシューフの方法に改良を加える前の歴史的文脈で見る必要があります。

コブリッツが指摘する2つ目の問題は、上記のように点の数がkqの形である曲線Eを見つけることの難しさである。多項式的に多くの試行で適切なEを見つけられることを保証する定理は知られていない。mを含むハッセ区間上の素数の分布は 、重複度を持つ曲線を数える群順序での素数の分布と同じではない。しかし、これは実際には大きな問題ではない。^[8]${\displaystyle [p+1-2{\sqrt {p}},p+1+2{\sqrt {p}}]}$

1993 年の論文で、アトキンとモレインは、面倒な点数計算アルゴリズム (シューフのアルゴリズム) に頼る手間を省いた ECPP アルゴリズムについて説明しました。このアルゴリズムは、上記の命題に依存していますが、楕円曲線をランダムに生成して適切なmを探すのではなく、点の数を簡単に計算できる曲線 Eを構築するというアイデアでした。曲線の構築では、 複素乗算が鍵となります。

ここで、素数であることを証明する必要があるNが与えられたら、ゴールドワッサー・キリアンテストと同様に、命題を満たし、Nの素数であることを証明できる適切なmとqを見つける必要があります。(もちろん、点Pと曲線自体Eも見つけなければなりません。)

ECPP は複素乗算を使用して曲線Eを構築し、 m ( E上の点の数) を簡単に計算 できるようにします。次にこの方法について説明します。

複素乗算を利用するには、負の判別式D が必要です。D は、 2 つの要素の積として表すことができます 。または、完全に同等に、次の式で表すことができます。 ${\displaystyle D=\pi {\bar {\pi }}}$

${\displaystyle a^{2}+|D|b^{2}=4N\,}$

あるa、bに対して、 N をこれらの形式のいずれかで記述できる場合、複素乗算 (詳細は後述) を使用して楕円曲線 E を作成できます。点の数は次のように与え られます。${\displaystyle \mathbb {Z} /N\mathbb {Z} }$

${\displaystyle |E(\mathbb {Z} /N\mathbb {Z} )|=N+1-\pi -{\bar {\pi }}=N+1-a.\,}$

N が2 つの元に分裂するためには、 （ここで はルジャンドル記号を表す）であることが必要である。これは必要条件であり、の位数の類数h ( D ) が 1 であれば十分条件が達成される。これはDの 13 個の値、つまり {−3, −4, −7, −8, −11, −12, −16, −19, −27, −28, −43, −67, −163} の元に対してのみ起こる。 ${\displaystyle \left({\frac {D}{N}}\right)=1}$${\displaystyle \left({\frac {D}{N}}\right)}$ ${\displaystyle \mathbb {Q} ({\sqrt {D}})}$

判別式Dをh ( D )の昇順で選びます。各Dについて、 4Nが次のように書ける かどうかを確認します。${\displaystyle \left({\frac {D}{N}}\right)=1}$

${\displaystyle a^{2}+|D|b^{2}=4N\,}$

この部分は、コルナッキアのアルゴリズムを使用して検証できます。受け入れ可能なDとaが見つかったら、を計算します。ここで、mにサイズ qの素因数がある場合、${\displaystyle m=N+1-a}$

${\displaystyle q>(N^{1/4}+1)^{2}}$

複素乗法を使って曲線Eとその上の点P を構築します。次に、この命題を使ってNの素数性を検証できます。mに大きな素因数がない場合や、十分に速く因数分解できない場合は、 Dの別の選択を行うことができます。^[1]

完全を期すために、 D (2 つの要素の積として表すことができます) が与えられた場合に楕円曲線を作成する方法である複素乗算の概要を説明します。

まず、およびであると仮定します（これらのケースははるかに簡単に行うことができます）。判別式Dの順序のh ( D ) クラスの楕円j 不変量を複素数として計算する必要があります。これらを計算するための式はいくつかあります。 ${\displaystyle D\neq -3}$${\displaystyle D\neq -4}$

次に、 h ( D ) 値に対応する根を持つモニック多項式 を作成します。これはクラス多項式であることに注意してください。複素乗法理論から、 には整数係数があることがわかっているので、これらの係数を十分正確に推定して、真の値を発見することができます。 ${\displaystyle H_{D}(X)}$${\displaystyle H_{D}(X)}$${\displaystyle H_{D}(X)}$

ここで、Nが素数の場合、CM は、Nが 2 つの要素の積として分割さ れるようにDが選択されたという事実に基づいて、Nを法としてh ( D )個の線形因数の積に分割されることを示しています。j がN を法としてh ( D ) 個の根の 1 つである場合、E を次のように定義できます。 ${\displaystyle H_{D}(X)}$

${\displaystyle y^{2}=x^{3}-3kc^{2r}x+2kc^{3r},{\text{ where }}k={\frac {j}{j-1728}},}$

c はN を法とする任意の二次非剰余数であり、r は0 または 1 です。

根jが与えられた場合、 Eの非同型な選択肢はrの選択肢ごとに 1 つずつ、2つしかありません。これらの曲線の濃度は次のように表されます。

${\displaystyle |E(\mathbb {Z} /N\mathbb {Z} )|=N+1-a}$または^{[1] [10] [12]}${\displaystyle |E(\mathbb {Z} /N\mathbb {Z} )|=N+1+a}$

Goldwasser-Killian テストと同様に、このテストはダウンラン手順につながります。ここでも、犯人はqです。機能するq が見つかったら、それが素数であることを確認する必要があります。そのため、実際には、この時点でqに対してテスト全体を実行します。その後、 qの因数に対するテストを実行する必要がある場合があります。これにより、各レベルに楕円曲線E、m、および疑わしい素数 qがあるネストされた証明書が生成されます。

Atkin–Morain ECPP テストを使用して が素数であることを証明する例を作成します。まず、13 個の可能な判別式の集合を順に調べ、ルジャンドル記号 かどうか、および 4 N がと表記できるかどうかをテストします。 ${\displaystyle N=167}$${\displaystyle (D/N)=1}$${\displaystyle 4N=a^{2}+|D|b^{2}}$

この例ではが選択されています。これは であり、また、Cornacchia のアルゴリズムを使用すると であり、したがってa = 25 かつb = 1 であることがわかっているためです。 ${\displaystyle D=-43}$${\displaystyle (D/N)=(-43/167)=1}$${\displaystyle 4\cdot (167)=25^{2}+(43)(1^{2})}$

次のステップはm を計算することです。これは次のように簡単に実行でき、次の式が得られます。次に、 mの素因数であるq を見つける必要があります。これは次の条件を満たしている必要があります。${\displaystyle m=N+1-a}$${\displaystyle m=167+1-25=143.}$${\displaystyle q>(N^{1/4}+1)^{2}.}$

この場合、m = 143 = 11×13です。したがって、残念ながら、必要な不等式を満たさないため、qとして11または13を選択することはできません。しかし、Morainの論文^[13]に由来するGoldwasser-Kilianアルゴリズムの前に述べたものと類似した命題によって、私たちは救われます。それは、mが与えられたとき、 mを割り切るが必ずしも素数ではないsを探し、 sを割り切る各sについて、${\displaystyle s>(N^{1/4}+1)^{2}}$${\displaystyle p_{i}}$

${\displaystyle (m/p_{i})P\neq P_{\infty }}$

まだ構築されていない曲線上の 点Pについて。

s が不等式を満たし、その素因数が上記を満たす場合、 Nは素数です。

したがって、私たちの場合、s = m = 143を選択します。したがって、可能な は11と13です。まず、 であることは明らかであり、したがって、 の値を確認するだけで済みます。 ${\displaystyle p_{i}}$${\displaystyle 143>(167^{1/4}+1)^{2}}$

${\displaystyle (143/11)P=13P\qquad {\text{ and }}\qquad (143/13)P=11P.}$

しかし、これを行う前に、曲線を作成し、点Pを選択する必要があります。曲線を作成するために、複素乗算を使用します。この場合、J不変量を計算し

${\displaystyle j\equiv -960^{3}{\pmod {167}}\equiv 107{\pmod {167}}.}$

次に計算する

${\displaystyle k={\frac {j}{1728-j}}{\pmod {167}}\equiv 158{\pmod {167}}}$

そして楕円曲線は次の形式であることが分かっています。

${\displaystyle y^{2}=x^{3}+3kc^{2}x+2kc^{3}}$、

ここでkは前述の通りであり、cは平方でない。したがって、 ${\displaystyle \mathbb {F} _{167}}$

${\displaystyle {\begin{aligned}r&=0\\3k&\equiv 140{\pmod {167}}\\2k&\equiv 149{\pmod {167}}\end{aligned}}}$

その結果

${\displaystyle E:y^{2}=x^{3}+140x+149{\pmod {167}}}$

ここで、 E上の点P = (6,6)を利用すると、${\displaystyle 143P=P_{\infty }.}$

13(6, 6) = (12, 65) かつ 11 P = (140, 147)であることは簡単に確認できるので、モレインの命題によれば、Nは素数です。

ゴールドワッサーとキリアンの楕円曲線素数性証明アルゴリズムは、少なくとも期待多項式時間で終了する。

${\displaystyle 1-O\left(2^{-N{\frac {1}{\log \log n}}}\right)}$

プライム入力の。

xより小さい素数の個数をxとする${\displaystyle \pi (x)}$

${\displaystyle \exists c_{1},c_{2}>0:\pi (x+{\sqrt {x}})-\pi (x)\geq {\frac {c_{2}{\sqrt {x}}}{\log ^{c_{1}}x}}}$

十分に大きいxに対して。

この予想を受け入れると、ゴールドワッサー・キリアンアルゴリズムは、あらゆる入力に対して期待多項式時間で終了します。また、Nの長さがkの場合、アルゴリズムはで検証できるサイズの証明書を作成します。^[14]${\displaystyle O(k^{2})}$${\displaystyle O(k^{4})}$

ここで、アルゴリズムの合計時間の上限を与える別の推測を考えてみましょう。

正の定数とが存在し、区間内の素数の数が ${\displaystyle c_{1}}$${\displaystyle c_{2}}$

${\displaystyle [x,x+{\sqrt {2x}}],x\geq 2}$ より大きい ${\displaystyle c_{1}{\sqrt {x}}(\log x)^{-c_{2}}}$

そして、ゴールドワッサー・キリアンアルゴリズムは、 Nの素数性を期待時間で証明する。

${\displaystyle O(\log ^{10+c_{2}}n)}$^[13]

アトキン・モレインアルゴリズムの場合、実行時間は次のように示される。

${\displaystyle O((\log N)^{6+\epsilon })}$一部の人々にとって^[3]${\displaystyle \epsilon >0}$

数の形によっては、素数証明への「近道」を見つけることが可能です。これはメルセンヌ数の場合です。実際、素数性の検証を容易にする特殊な構造のため、知られている 6 つの最大の素数はすべてメルセンヌ数です。^{[15]メルセンヌ数の素数性を検証する方法は、}ルーカス・レーマー テストとして長い間使用されてきました。このテストは楕円曲線に依存しません。ただし、 、n が奇数の形式の数が楕円曲線を使用して素数 (または合成数) であることを証明できるという結果を示します。もちろん、これはn = 1の場合に対応するメルセンヌ数の素数性を証明する方法も提供します。次の方法は、津村雄の論文「楕円曲線を使用した素数性テスト」から引用したものです。^[16]${\displaystyle N=2^{k}n-1}$${\displaystyle k,n\in \mathbb {Z} ,k\geq 2}$${\displaystyle 2^{k}n-1}$

E を楕円曲線とします。ここで、 Eは の形式で、は素数、 は奇数です。 ${\displaystyle y^{2}=x^{3}-mx}$${\displaystyle m\in \mathbb {Z} ,m\not \equiv 0{\bmod {p}},}$${\displaystyle p\equiv 3{\bmod {4}}}$${\displaystyle p+1=2^{k}n,}$${\displaystyle k\in \mathbb {Z} ,k\geq 2,n}$

定理1. ^[7] ${\displaystyle |E(\mathbb {F} _{p})|=p+1.}$

定理 2. または、m がp を法とする平方剰余であるかどうかによって異なります。${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n}}$${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2}\oplus \mathbb {Z} _{2^{k-1}n}}$

定理3. E上のQ = ( x , y )が、 x がpを法とする2次の非剰余となるようなものとする。このとき、 Qの位数は巡回群において${\displaystyle 2^{k}}$${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n}.}$

まず、 nが に対して比較的小さい場合を示しますが、これにはもう 1 つの定理が必要になります。 ${\displaystyle 2^{k}}$

定理4.を選択し、 ${\displaystyle \lambda >1}$

${\displaystyle n\leq {\frac {\sqrt {p}}{\lambda }}\qquad {\text{and}}\qquad \lambda {\sqrt {p}}>\left({\sqrt[{4}]{p}}+1\right)^{2}.}$

このとき、E上にQ = ( x , y )が存在し、 i = 1, 2, ..., k  − 1に対して となる場合、および が初期値を持つシーケンスである場合に限り、 pは素数です。${\displaystyle \gcd {(S_{i},p)}=1}$${\displaystyle S_{k}\equiv 0{\pmod {p}},}$${\displaystyle S_{i}}$${\displaystyle S_{0}=x}$

ここでは、主に定理 3 と 4 に基づいた次のアルゴリズムを示します。指定された数が素数であるかどうかを確認するには、次の手順を実行します。 ${\displaystyle N}$

(1)となるものを選び、 となるものを見つける。 ${\displaystyle x\in \mathbb {Z} }$${\displaystyle \left({\frac {x}{N}}\right)=-1}$${\displaystyle y\in \mathbb {Z} ,y\not \equiv 0{\pmod {2}}}$${\displaystyle \left({\frac {x^{3}-y^{2}}{N}}\right)=1}$

を取って 。 ${\displaystyle m={\frac {x^{3}-y^{2}}{x}}\mod N}$${\displaystyle m\not \equiv 0{\pmod {N}}}$

それから です。 ${\displaystyle Q'=(x,y)}$${\displaystyle E:y^{2}=x^{3}-mx}$

を計算します。 が合成数である場合は(2)に進みます。 ${\displaystyle Q=nQ'}$${\displaystyle Q\in E}$${\displaystyle N}$

（２） を初期値として数列に 設定し、について計算する。 ${\displaystyle S_{i}}$${\displaystyle Q}$${\displaystyle S_{i}}$${\displaystyle i=}$${\displaystyle 1,2,3,...,k-1}$

に対して が成り立つ場合、 は合成数である。それ以外の場合は(3)に進む。 ${\displaystyle \gcd({S_{i},N})>1}$${\displaystyle i}$${\displaystyle 1\leq i\leq k-1}$${\displaystyle N}$

(3) の場合、は素数です。そうでない場合は、は合成数です。これでテストは完了です。 ${\displaystyle S_{k}\equiv 0{\pmod {N}}}$${\displaystyle N}$${\displaystyle N}$

(1)では、楕円曲線Eと、 E上の点Qが選ばれ、Qのx座標が2次非剰余となる。

${\displaystyle \left({\frac {m}{N}}\right)=\left({\frac {\frac {x^{3}-y^{2}}{x}}{N}}\right)=\left({\frac {x}{N}}\right)\left({\frac {x^{3}-y^{2}}{N}}\right)=-1\cdot 1=-1.}$

したがって、Nが素数の場合、定理 3 により、 Q' はで割り切れる位数を持ち、したがってQ'の位数はd | nです。 ${\displaystyle 2^{k}}$${\displaystyle 2^{k}d}$

これは、 Q = nQ' がの位数を持つことを意味します。したがって、(1) でNが合成数であると結論付けられた場合、N は合成数です。(2) と (3) で、 Q がの位数を持つかどうかを確認します。したがって、(2) または (3) でNが合成数であると結論付けられた場合、N は合成数です。 ${\displaystyle 2^{k}}$${\displaystyle 2^{k}}$

ここで、アルゴリズムがNが素数であると結論付けた場合、それは定理 4 の条件を満たすことを意味し、したがってN は真に素数です。 ${\displaystyle S_{1}}$

nが大きい場合のアルゴリズムも存在しますが、これについては前述の論文を参照してください。^[16]

• Atkinと Morainによる「楕円曲線と素数性の証明」 。
• Weisstein、Eric W.「楕円曲線の素数性の証明」。MathWorld。
• Chris Caldwell、「素数証明 4.2: 楕円曲線と ECPP テスト」( Prime Pages)。
• François Morain、「ECPP ホームページ」(一部のアーキテクチャ用の古い ECPP ソフトウェアが含まれています)。
• Marcel Martin、「Primo」（Linux 64 ビット用バイナリ）
• PARI/GP、アトキン・モラン素数およびプリモ素数証明書を作成する機能を備えたコンピュータ代数システム
• GMP-ECPP、無料のECPP実装
• LiDIA、 ECPP をサポートする Linux 用の無料C++ライブラリ
• CM、ECPP実装を含む別の無料ライブラリ