正規化されたアイゼンシュタイン級数を以下で定義する。
は以下で定義されるベルヌーイ数である。
シグマはnの全ての約数dのべきの和を取る約数関数である。
次数の小さい方から例を書くと、
j関数を以下で定義します。
このj関数は複素数体上の関数ですが、
有限体(qは素数のべき)上の楕円曲線のと本質的に等しいです。
j関数の別の表現も知られています。
この証明にはモジュラー形式(Modular Form)の理論を使います。
どちらの形もj関数の係数を求めるのに使えそうですが、2番目の方を使うことにします。
コンピュータで計算する場合のアルゴリズムを考えてみます。
1) 1変数有限次多項式を実装する。
2) 正規化されたアイゼンシュタイン級数の指定最低次数までを返す関数を実装する。
3) を正規化されたデルタ関数と呼ぶことにして(この名前はこのブログ内でのみ通用する用語です。)
正規化されたデルタ関数 の指定最低次数までを返す関数を実装します。
4) のようにして分母の値を指定最低次数までの分子の値して返す関数を実装する。
5) j(q) q をqの指定次数まで計算してqのべきの係数を答えとします。
### rustで実装してみた
#[test] fn j_invariant_test1() { assert_eq_str!(j_invariant1(&BigInt::from(2)), "196884 x^2 + 744 x + 1"); assert_eq_str!(j_invariant1(&BigInt::from(3)), "21493760 x^3 + 196884 x^2 + 744 x + 1"); assert_eq_str!(j_invariant1(&BigInt::from(4)), "864299970 x^4 + 21493760 x^3 + 196884 x^2 + 744 x + 1"); assert_eq_str!(j_invariant1(&BigInt::from(5)), "20245856256 x^5 + 864299970 x^4 + 21493760 x^3 + 196884 x^2 + 744 x + 1"); }
デバッグビルドで5次の計算で30秒くらいかかりますが、なんとか実装できました。
かなり無駄な計算をしているので、最適化の余地は残っています。
ソースはこちらです。
GitHub - pebble8888/ellipticcurve