Schoof-Elkies-Atkin アルゴリズム

シューフ・エルキーズ・アトキンアルゴリズム（SEA）は、有限体上の楕円曲線上の点の順序を求めたり、点の数を計算したりするアルゴリズムです。主な応用は楕円曲線暗号です。このアルゴリズムは、ノーム・エルキーズとAOL・アトキンによってシューフのアルゴリズムが拡張され、（ヒューリスティックな仮定の下で）効率が大幅に向上しました。

詳細

ショーフのアルゴリズムに対するエルキーズ-アトキン拡張は、考慮する素数の集合を特定の種類の素数に制限することで機能します。これらはそれぞれエルキーズ素数、アトキン素数と呼ばれるようになりました。特性方程式 が で分解される場合、素数はエルキーズ素数と呼ばれ、アトキン素数はエルキーズ素数ではない素数と呼ばれます。アトキンは、アトキン素数から得られる情報とエルキーズ素数から得られる情報を組み合わせて、ショーフ-エルキーズ-アトキン アルゴリズムとして知られるようになる効率的なアルゴリズムを作成する方法を示しました。取り組むべき最初の問題は、与えられた素数がエルキーズ素数かアトキン素数かを判断することです。そのためには、j 不変量に関して-同質楕円曲線のペアをパラメータ化するモジュラー多項式を使用します(実際には、同じ目的で別のモジュラー多項式を使用することもできます)。 ${\displaystyle S=\{l_{1},\ldots ,l_{s}\}}$ ${\displaystyle l}$ ${\displaystyle \phi ^{2}-t\phi +q=0}$ ${\displaystyle \mathbb {F} _{l}}$ ${\displaystyle \Phi _{l}(X,Y)}$ ${\displaystyle l}$

例示された多項式が に根を持つ場合、はエルキーズ素数であり、からまでの -同値系の核内の点に根が対応する多項式を計算できます。この多項式は、シューフのアルゴリズムで使用される対応する除算多項式の約数であり、と比較して次数が大幅に低くなります。エルキーズ素数の場合、これによって、 を法とする の点の数をシューフのアルゴリズムよりも効率的に計算できます。アトキン素数の場合は、におけるの因数分解パターンからいくつかの情報を取得できます。これは、 を法とする点の数の可能性を制約しますが、アルゴリズムの漸近的複雑さはエルキーズ素数に完全に依存します。小さなエルキーズ素数が十分に多い場合 (平均して、素数の半分がエルキーズ素数であると予想されます)、これによって実行時間が短縮されます。結果として得られるアルゴリズムは確率的（ラスベガス型）であり、その期待実行時間は経験的に であるため、 Schoofのアルゴリズムよりも実用的に効率的です。ここでの表記法は、式の主項において対数的な項を省略する ビッグオー表記法の変形です。${\displaystyle \Phi _{l}(X,j(E))}$ ${\displaystyle j(E')}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle l}$ ${\displaystyle f_{l}(X)}$ ${\displaystyle l}$ ${\displaystyle E}$ ${\displaystyle E'}$ ${\displaystyle f_{l}}$ ${\displaystyle O(l)}$ ${\displaystyle O(l^{2})}$ ${\displaystyle E}$ ${\displaystyle l}$ ${\displaystyle \Phi _{l}(X,j(E))}$ ${\displaystyle \mathbb {F} _{l}[X]}$ ${\displaystyle l}$ ${\displaystyle l}$ ${\displaystyle {\tilde {O}}(\log ^{4}q)}$ ${\displaystyle {\tilde {O}}}$

実装

Schoof–Elkies–Atkin アルゴリズムは、 GP 関数 ellap のPARI/GPコンピュータ代数システムに実装されています。

外部リンク

• 「Schoof: 有限体上の楕円曲線上の点の数え上げ」
• Mathworldの記事
• 「Schoof-Elkies-Atkinアルゴリズムに関する考察」
• 「特性2におけるSEAアルゴリズム」