AKS Variant

AKS アルゴリズムは決定的多項式時間で素数判定を実現したことで有名ですが、実際の判定時間は膨大になるため、実用的でないことが知られています。この AKS アルゴリズムを楕円曲線上で言い換えた感じの variant が Couveignes たちによって提案されているのを知りました。確率的になってしまうものの、高速なのが売りのようです。といっても 1024 ビット整数の判定に 12 時間ほど必要なようですが。論文をななめ読みすると、これまでにもいろいろな variant が提案されていたのですね。久しぶりに勉強したくなってきました...