Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

有限体の3等分点の例

 F_{23}上のy^{2} = x^{3}  + x + 7の3等分点を考えます。
3等分点は9つあります。(一つは無限遠点です。)
そのうちの2つをP, Qとします。
 P:(1, 3)
 Q:(14, \sqrt {5})
 1^{3} + 1 + 7 = 9なのでPが曲線上にあることはすぐ確かめられます。
 14^{3} + 14 + 7 = 2765 \mod 23 = 5 なので、Qも曲線上にあることが分かります。

ちなみに、この計算はmac book上のpython3で以下のように確認しています。

$ 14 **3 + 14 + 7
2765
$ _%23
5

pythonでは最後の計算結果がアンダースコア(_)に入るようになっています。
これを使うと括弧をタイプすることなく有限体上の値が求められるので便利です。

2つの点が等しい時と等しくない時の点の加算公式
 y^{2} = x^{3} + A x + B
 x_3 = m^{2} - x_1 - x_2
 y_3 = m (x_1 - x_3) - y_1
 m = \frac {y_2 - y_1} {x_2 - x_1}
 x_3 = m^{2} - 2 x_1
 y_3 = m(x_1 - x_2) - y_1
 m = \frac {3 {x_1}^{2} + A} {2 y_1}
を使って、残りの点を求めると以下のようになります。
 2P = (1, -3)
 2Q = (14, - \sqrt {5})
 P + Q = (4 + 5 \sqrt {5}, 17 + 8 \sqrt {5})
 2P + 2Q = (4 + 5 \sqrt {5}, -17 -8 \sqrt {5})
 2P + Q = (4 + 18 \sqrt {5}, 3 + 7 \sqrt {5})
 P + 2Q = (4 + 18 \sqrt {5}, -3 -7 \sqrt {5})

ここで、 O, P, 2P, Q, 2Q, P+Q, 2P+2Q, 2P+Q, P+2Q
は3倍するとOになることも確かめられます。
3等倍点の群の部分群は、n+1=4個あるはずで、以下の4つです。
 C_1 = \{ O, P, 2P \}
 C_2 = \{ O, Q, 2Q \}
 C_3 = \{ O, P+2Q, 2P+Q \}
 C_4 = \{ O, P, Q \}

これらの部分群のうち、点が全て F_{23}の範囲に入っている群は C_1 = \{ O, P, 2P \}だけです。
 \sqrt {5} F_{23}の範囲には入っていませんが、 F_{23^{2}}の範囲には入っています。
規約多項式 x^{2} - 5を使って F_{23}を拡大したものが F_{23^{2}}です。
素体を拡大する - Pebble Coding


フロべニウス写像 \phi_{23}: (x, y) \rightarrow (x^{23}, y^{23})を考えます。
点P, 2Pはこの写像でxの値もyの値も変化しません。なぜなら、
 1^{23} = 1, 3^{23} = 3, (-3)^{23} = -3が成り立つからです。
つまり、 \phi_{23} P = P, \phi_{23} 2P = 2P
それ以外の点は変化します。

 (\sqrt {5})^{23} = 5^{11} \sqrt {5} = 22 \sqrt {5} = - \sqrt {5}
 (-\sqrt {5})^{23} = \sqrt {5}
 (4 + 5 \sqrt {5})^{23} = 4 + 18 \sqrt {5}
 (4 + 18 \sqrt {5})^{23} = 4 + 5 \sqrt {5}
 (17 + 8 \sqrt {5})^{23} = 17 + 5 \sqrt {5}
 (3 + 7 \sqrt {5})^{23} = 3 + 16 \sqrt {5}
 (17 + 5 \sqrt {5})^{23} = 17 + 18 \sqrt {5}
 (3 + 16 \sqrt {5})^{23} = 3 + 7 \sqrt {5}

ちなみにこの計算はsagemathで以下のようにして計算しました。

sage: ((4 + 5 * sqrt(5))**23).simplify_full()
330338668096295889998183465*sqrt(5) + 738659668331383149542529164
sage: a =738659668331383149542529164
sage: b =330338668096295889998183465
sage: a %23
4
sage: b % 23
18

別の方法もあります。

sage: K.<alpha> = QuadraticField(5)
sage: (4 +  5 * alpha)**23
330338668096295889998183465*alpha + 738659668331383149542529164


おそらく、そのものズバリの書き方があると思うのですが、分かりませんでした。

 \phi (Q) = \phi (14, \sqrt {5}) = (14, - \sqrt {5}) = -Q
 \phi (2Q) = \phi (14, - \sqrt {5}) = (14, \sqrt {5}) = -2Q
 \phi (P+Q) = \phi (4 + 5 \sqrt {5}, 17 + 8 \sqrt {5}) = (4 + 18 \sqrt {5}, 17 + 5 \sqrt {5})
 \phi (2P+2Q) = (4+18 \sqrt {5}, -17 - 5 \sqrt {5})
 \phi (2P+Q) = \phi(4+18 \sqrt {5}, 3+7 \sqrt {5}) = (4+5 \sqrt {5}, 3 + 16 \sqrt {5})
 \phi (P+2Q) = \phi(4+18 \sqrt {5}, -3-7 \sqrt {5}) = (4+5 \sqrt {5}, -3 -16 \sqrt {5})
 {\phi}^{2} (P+Q) = \phi (4+18 \sqrt {5}, 17 + 5 \sqrt {5}) = (4 + 5 \sqrt {5}, 17+18 \sqrt {5}) = P+Q
 {\phi}^{2} (2P+2Q) = \phi (4 +18 \sqrt {5}, -17 -5 \sqrt) = (4 + 5 \sqrt {5}, -17 -18 \sqrt {5}) = 2P+2Q
 {\phi}^{2} (2P+Q) = \phi (4  +5 \sqrt {5}, 3 + 16 \sqrt {5}) = (4 + 18 \sqrt {5}, 3 + 7 \sqrt {5}) = 2P +Q
 {\phi}^{2} (P+2Q) = P+2Q

この計算結果を用いると、フロべニウス写像は、点Pと点2Pは変化させない。
点Qは点-Qへ、点2Qは点-2Qへ変化させる。
残りの4つの点は F_{23^{2}}上の楕円曲線上にはあるが3等倍点以外の点に変化させる。
4つの点はフロべニウス写像を2回施すと、自分自身の点に戻る。  
ということが分かります。

sagemath で3等分点を計算する

体拡大の要素は選べませんが、sagemathのコマンドで3等分点を求めることもできます。
ここでaは b + c \sqrt {d}のような何らかの値だと思うのですが、具体的な値は分かりません。

sage: K.<a> = GF(23**2)
sage: E = EllipticCurve(K, [1, 7])
sage: E.j_invariant()
18
sage: P=E(0)
sage: P.division_points(3)
[(0 : 1 : 0),
 (1 : 3 : 1),
 (1 : 20 : 1),
 (14 : 4*a + 19 : 1),
 (14 : 19*a + 4 : 1),
 (3*a + 1 : 9*a + 20 : 1),
 (3*a + 1 : 14*a + 3 : 1),
 (20*a + 7 : 9*a + 8 : 1),
 (20*a + 7 : 14*a + 15 : 1)]
sage: P.division_points(5)
[(0 : 1 : 0),
 (8 : 9*a + 14 : 1),
 (8 : 14*a + 9 : 1),
 (17 : 5*a + 18 : 1),
 (17 : 18*a + 5 : 1)]

プライバシーポリシー

お問い合わせ

スポンサーリンク