同種写像の例 - Pebble Coding

What is an isogeny of elliptic curves?

こちらの記事に同種写像(isogeny)の例がのっています。
$E_2 : y^{2} = x^{3} + 1132 x + 278$
$E_4 : Y^{2} = X^{3} + 500 X + 1005$
$F_{2003}$

$(x, y) \rightarrow (\frac {x^{2} + 301 x + 527} {x + 301}, \frac {y x^{2} + 602 y x + 1942 y} {x^{2} + 602 x + 466})$
この写像のxの部分の分母、分子で次数が大きい方が2なので、
この同種写像の次数(degree)は2ということになります。

この変換式が本当に同種写像かどうかを確かめるには、変換式の点が $E_4$ の式を満たすかどうかを確かめればよいですが、
xの次数は最大10くらいになるので、手計算ではしんどいです。
そこで自作した多項式ライブラリで計算してみました。

#[test]
fn isogeny_test() {
    use super::termbuilder;
    type TermBuilder = termbuilder::TermBuilder;

    let a = BigInt::from(1132);
    let b = BigInt::from(278);
    let pp = BigInt::from(2003);

    let e1 = TermBuilder::new().coef(1).ypow(2).build();

    let p = TermBuilder::new().coef(1).xpow(2).build()
    + TermBuilder::new().coef(301).xpow(1).build()
    + TermBuilder::new().coef(527).build();

    let q = TermBuilder::new().coef(1).xpow(1).build()
    + TermBuilder::new().coef(301).build();

    let r = TermBuilder::new().coef(1).xpow(2).build()
    + TermBuilder::new().coef(602).xpow(1).build()
    + TermBuilder::new().coef(1942).build();

    let s = TermBuilder::new().coef(1).xpow(2).build()
    + TermBuilder::new().coef(602).xpow(1).build()
    + TermBuilder::new().coef(466).build();

    let sum = &e1 * r.power(2) * q.power(3)
    - p.power(3) * s.power(2)
    - TermBuilder::new().coef(500).build() * p * s.power(2) * q.power(2)
    - TermBuilder::new().coef(1005).build() * s.power(2) * q.power(3);
    let sum = sum.reduction_modular(&a, &b, &pp);
    assert_eq_str!(sum, "0");
}

/develop/modular-polynomial/src (master *)$ cargo test isogeny_test
   Compiling moduler-polynomial v0.1.0 (/develop/modular-polynomial)
    Finished dev [unoptimized + debuginfo] target(s) in 1.02s
     Running /develop/modular-polynomial/target/debug/deps/moduler_polynomial-2955192f700f401a

running 1 test
test polynomial::isogeny_test ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 13 filtered out

分母分子をp, q, r, sとおき、最終的な分子だけを計算して0に等しいかどうかを調べています。
うまく行きました。
ごちゃごちゃするのが難点ですが、pythonより単体テストやりやすいし、無駄に手計算する時間が省けて助かります。

SageMath

余談ですが、SageMathで2倍点を確認しておきます。

sage: E = EllipticCurve(GF(2003), [1132, 278])
sage: E.cardinality()
1956
sage: O = E(0)
sage: O.division_points(2)
[(0 : 1 : 0), (1702 : 0 : 1)]

sage: E2 = EllipticCurve(GF(2003), [500, 1005])
sage: E2.cardinality()
1956
sage: O2 = E2(0)
sage: O2.division_points(2)
[(0 : 1 : 0), (602 : 0 : 1), (1575 : 0 : 1), (1829 : 0 : 1)]

isogenyはどうやって作るか

今回のisogenyは次の関係式を満たしています。
$(\frac {p(x)} {q(x)}, y (\frac {p(x)} {q(x)})')$
ダッシュはxでの微分です。

$p(x) = x^{2} + 301 x + 527$
$q(x) = x + 301$
$(\frac {p(x)} {q(x)})' = \frac {p'q - pq'} {q^{2}} = \frac {(2x + 301) (x +301) - (x^{2} + 301 x + 527)} {x^{2} + 602 x + 90601} = \frac {x^{2} + 602 x + 90074} {x^{2} + 602 x + 90601}$
$= \frac {x^{2} + 602 x + 1942} {x^{2} + 602 x + 466}$

等倍点

sage: factor(1956)
2^2 * 3 * 163