Velu's Formula - Pebble Coding

isogeny関連でvelu's formulaというものがあります。
まずは、体についてのおさらいをしておきます。
体Kは標数が0または素数pです。
標数の定義
体Kの乗法の単位元 $1_K$ を標数 $ch(K)$ 個加算したものが加法の単位元 $0_K$ になるということです。
$1_K + 1_K + ... + 1_K = 1_K \times ch(K) = 0_K$
$1_K$ をどれだけ足しても $0_K$ にならない場合は標数0と定義します。

ここでは有限体にしか興味がないので、標数は素数pとなります。
有限体の場合、その体の元の個数は素数べきになります。
qを素数とすると元の個数は $q, q^{2}, q^{3}, ...$ のいずれかということになります。

Velu's formulaを簡略化したものを大雑把に言うと次のようになります。
$y^{2} = x^{3} + a x + b$ で与えられる体K上の楕円曲線 $E_1$ に対して、
$E_1(\overline K)$ 楕円曲線の有限部分群Cを考える。
$E_1$ から $E_2$ への分離可能な同種写像 $\alpha$ が存在し、それは $C = Ker(\alpha)$ を満たす。

$y^2 = x^3 + a x + b$
$g_p^x = 3 x_P^2 + a$
$g_P^y = -2y_P$
$v_P = g_P^x (if 2P = O)$
$v_P = 2 g_P^x (if 2P \ne O)$
$u_P = (g_P^y)^2$
$v = \sum_{P \in S} v_P$
$w = \sum_{P \in S} (u_P + x_P v_P)$
$C = O \cup C_2 \cup F_{+} \cup F_{-}$
Cは部分群、 $C_2$ は2等分点、 $F_{+}$ は $F_{-}$ のyの値をマイナス化したものです。
$S = C_2 \cup F_{+}$
$Y^2 = X^3 + (a-5v) X + (b-7w)$
$X = x + \sum_{P \in S} ( \frac {v_P} {x - x_P} + \frac {u_P} {(x-x_P)^2})$
$Y = y - \sum_{P \in S} ( \frac {2 u_P y} {(x - x_P)^3} + \frac {v_P (y- y_P) - g_P^x g_P^y } {(x-x_P)^2} )$
コンピュータで計算する場合は、部分群の全ての有理点の計算が必要ということになります。

Velu's formulaでは体Kとなっていますが、今は有限体にしか興味がないので、体Kは有限体とします。
体Kは $F_p$ (pは素数)や $F_{p^{2}}$ ということになりますが、ここでは $F_p$ の場合を考えます。
有限体の閉包の部分群となると、一番簡単なのが、 $F_p$ (pは素数)で、その次が、 $F_{p^{2}}$ となりますが、
こちらの部分群も $F_p$ を考えます。

次の定理が成り立ちます。
次の２つは同値である。
1. $F_q$ (qは素数べき)上の２つの楕円曲線 $E_1, E_2$ について、２つの楕円曲線の有理点の数が等しい。
2. $E_1, E_2$ は同種写像である。

以下２つの楕円曲線を $F_{2003}$ 上で考えると、どちらの楕円曲線も位数は1956である。
1956を素因数分解すると以下のようになる。
$1956=2 \times 2 \times 3 \times 163$

$y^2 = x^3 + 1132 x + 278$
$y^2 = x^3 + 500 x + 1005$

Velu's formulaで同種写像を求めるには、位数1956の群の部分群を考ることになるが、手計算でもできるように位数2を考える。
ちなみに、位数が小さい有理点を以下にあげておく。

P1671 (1702, 0) order 2
P495 (522, 89) order 3
P496 (522, 1914) order 3
P629 (637, 385) order 4
P630 (637, 1618) order 4
P931 (936, 842) order 6
P932 (936, 1161) order 6
P1209 (1207, 720) order 12
P1210 (1207, 1283) order 12

位数２の同種写像

位数2の部分群は無限遠点を除くと1点しかないので和は一つでよいので計算が楽である。
位数2のisogenyを計算してみよう。
$(x_{P1671}, y_{P1671}) = (1702, 0) = (1702-2003,0) = (-301, 0)$

a = 1132, b = 278
$g_P^{x} = 3 x_P^{2} + a = 3 \cdot (-301)^2 + 1132 (mod 2003) = 527$
$g_P^{y} = -2 y_P = -2 \cdot 0 = 0$
$v_P = g_P^{x} = 527$
$u_P = (g_P^{y})^{2} = 0$
$v = \sum_{P \in S} v_P = 527$
$w = \sum_{P \in S} (u_P + x_P v_P) = 0 - 301 \cdot 527 (mod 2003) = 1613$
$A = a - 5 v = 1132 - 5 \cdot 527 (mod 2003) = -1503 = 500$
$B = b - 7 w = 278 - 7 \cdot 1613 (mod 2003) = 278 - 11291 = -11013 = -998 = 1005$

ここまでで $Y^{2} = X^{3} + A x + B = X^{3} + 500 X + 1005$ であることが分かりました。
$X = x + \sum_{P \in S} ( \frac {v_P} {x-x_P} + \frac {u_P} {(x-x_P)^{2}})$
$= x + \frac {527} { x - (-301)} = x + \frac {527} {x + 301} = \frac {x^{2} + 301 x + 527} {x + 301}$
$Y = y - \sum_{P \in S} ( u_P \frac {2y} {(x- x_Q)^{3}} + v_P \frac {(y-y_P)} {(x-x_P)^{2}} + \frac {- g_P^x g_P^y} { (x - x_P)^{2}})$
$= y - (0 \cdot ... + 527 \frac {y - 0} {(x-(-301))^{2}} + \frac {- 527 \cdot 0} {...})$
$= y - 527 \frac {y} {(x+301)^{2}}$
$= y - 527 \frac {y} {x^2 + 602x + 90601}$
$= y - 527 \frac {y} {x^2 + 602x + 466}$
$= y \frac {x^2 + 602 x + 466 - 527} {x^2 + 602 x + 466}$
$= y \frac {x^2 +602 x - 61} {x^2 + 602 x + 466}$
$= y \frac {x^2 + 602 x - 61 + 2003} {x^2 + 602 x + 466}$
$= y \frac {x^2 + 602x + 1942} {x^2 + 602 x +466}$

同種写像の例 - Pebble Coding

位数３の同種写像

位数3の場合は無限遠点以外に2つの点がありますが、２つのxの値は同じなので、どちらか一つの点だけの和となり、計算が楽です。

$(x_{P495}, y_{P495}) = (522, 89)$
a= 1132,b = 278
${g_P}^x = 3 {x_P}^2 + a = 3 \cdot 522^2 + 1132 = 1360$
${g_P}^y = -2 {y_P} = -178$
$v_P = 2 (g_P)^x = 2 \cdot 1360 = 717$
$u_P = ({g_P}^y)^2 = (-178)^2 = 1639$
$v = \sum v_P = 717$
$w = \sum (u_P + x_P v_P) = 1639 + 522 \cdot 717 = 1352$
$A = a - 5 v = 1132 - 5 \cdot 717 = -450 = 1553$
$B = b - 7w = 278 - 7 \cdot 1352 = -1174 = 829$
$Y^2 = X^3 + 1553 X + 829$
$x + \frac { v_P } { x - x_P} + \frac {u_P} {(x-x_P)^2} = x + \frac {717} {x - 522} + \frac {1639} {(x-522)^2}$
$Y = y - (1639 \frac {2y} {(x-522)^{3}} + 717 \frac {y - 89} {(x-522)^2} + \frac { (-1360) (-178) } {(x-522)^2})$
$= y - (\frac {1275 y} {(x-522)^3} + \frac {717y - 1720 + 1720} {(x-522)^2})$
$= y - \frac {1275y} {(x-522)^3} - \frac {717y} {(x-522)^2}$