こちらモジュラー多項式の定義と係数の求め方 - Pebble Codingで
モジュラー多項式の係数を求めるアルゴリズムについて書きましたが、rustでの実装が完成しました。
めちゃくちゃ遅く実用化には程遠いですが、解説しておきます。
SageMathでの実装のアルゴリズムも基本同じはずなんだが。。
ソースはこちら
GitHub - pebble8888/ellipticcurve
レシピ
1. coef, x, y, q, c_i_jの多項式を実装する。
サイズがi64に収まりそうにないところはBigIntを用いる。
coefは整数係数、x, yは冪の大きさで整数、qは冪の大きさで整数、c_i_jは整数i, jを添字とする定数を表す。
2. j不変量のqの任意の次数までの多項式を実装する。
アイゼンシュタイン級数とデルタのqの任意の次数までの多項式を実装する。
3. 定数係数を含む一般式のX, Yにを代入してqの負のべきと0のべきの係数を0とおいた連立方程式を作る。
4. 連立方程式を解いて係数c_i_jを全て決定する。連立方程式はガウス法とピボット選択を使う。
$ cargo run --example hello_world
Compiling ellipticcurve v0.1.0 (/Users/pebble8888/develop/ellipticcurve)
Finished dev [unoptimized + debuginfo] target(s) in 1.31s
Running `target/debug/examples/hello_world`
x^3 - x^2 y^2 + 1488 x^2 y - 162000 x^2 + 1488 x y^2 + 40773375 x y + 8748000000 x + y^3 - 162000 y^2 + 8748000000 y - 157464000000000
x^4 - x^3 y^3 + 2232 x^3 y^2 - 1069956 x^3 y + 36864000 x^3 + 2232 x^2 y^3 + 2587918086 x^2 y^2 + 8900222976000 x^2 y + 452984832000000 x^2 - 1069956 x y^3 + 8900222976000 x y^2 - 770845966336000000 x y + 1855425871872000000000 x + y^4 + 36864000 y^3 + 452984832000000 y^2 + 1855425871872000000000 y
