Pebble Coding

プログラマーの作業メモ

素体上の楕円曲線の等分点をpythonで計算してみる

楕円曲線において n P = Oとなる点Pの集まりを等分点と呼びます。
左辺は点をn倍することを表し、右辺は無限遠点を表します。

python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Coding

以前使ったpythonスクリプトをちょっといじって計算してみました。
まずは、 y^{2} = x^{3} + x^{2} + 1 で 素体を F_5とします。

f:id:pebble8888:20170909165102p:plain

1 torsion Point:
2 torsion Point:
3 torsion Point:
 P3
 P4
4 torsion Point:
5 torsion Point:
6 torsion Point:
 P3
 P4
7 torsion Point:
8 torsion Point:

3等分点がP3, P4の2つ、6等分点がP3, P4の2つ見つかりましたが、無限遠点はn等分でもあるので、 3等分点がP3, P4, Oの3つ、6等分点がP3, P4, O の3つとなります。
ちなみに、この群の位数は9なので、全ての点は9倍すると無限遠点になります。

別の曲線でも試してみます。

 y^{2} = x^{3} + 2 + 4
 F_{13} 群位数17

1 torsion Point:
2 torsion Point:
3 torsion Point:
4 torsion Point:
5 torsion Point:
6 torsion Point:
7 torsion Point:
8 torsion Point:
9 torsion Point:
10 torsion Point:
11 torsion Point:
12 torsion Point:
13 torsion Point:
14 torsion Point:
15 torsion Point:
16 torsion Point:

等分点がひとつも見つかりませんでした。

最期です  y^{2} = x^{3} + 7
 F_{17} 群位数は18です。

f:id:pebble8888:20180706004659p:plain

1 torsion Point:
2 torsion Point:
 P5
3 torsion Point:
 P6
 P7
4 torsion Point:
 P5
5 torsion Point:
6 torsion Point:
 P5
 P6
 P7
 P10
 P11
7 torsion Point:
8 torsion Point:
 P5
9 torsion Point:
 P1
 P2
 P3
 P4
 P6
 P7
 P14
 P15
10 torsion Point:
 P5
11 torsion Point:
12 torsion Point:
 P5
 P6
 P7
 P10
 P11
13 torsion Point:
14 torsion Point:
 P5
15 torsion Point:
 P6
 P7
16 torsion Point:
 P5
17 torsion Point:

なんとなくイメージはつかめたでしょうか。
無限遠点はn等分点全てに含まれるので、n等分点の個数を数えてみると、
2->2
3->3
4->2
6->6
8->2
9->9
10->2
12->6
14->2
15->3
16->2
のようになっており、n等分点の点の個数はnの約数になっていることが分かります。

実は、n等分点だけからなる集合を考えると、有理点の群の部分群になっていることが知られています。
このn等分点だけからなる集合を E[n] と書きます。

楕円曲線の点の2倍公式

楕円曲線の点の2倍公式を楕円曲線を簡単にして計算してみよう。

楕円関数の加法公式 - Pebble Coding

で計算を簡単にするためa=0とする。2倍公式を得るにはP=Qとすれば良い。
すると、
 X = \frac {x^{4} - 8bx} {4(x^{3} + b)}
 Y = y \frac {x^{6} + 20b x^{3} - 8 b^{2}} {8 (x^{3} + b)} が得られる。
3倍公式、4倍公式を求めていくと、xの有理式の次数が上がっていくであろうことが想像できる。
また、Y は yが一つ現れるだけで、それ以外はxの有理式となることが分かる。

体論

  • 定義 1
    Kを体とする。任意の定数でない1変数多項式 f(x) \in K[x]に対し
     \alpha \in Kがあり f(\alpha) = 0となるとき、Kを代数閉体(algebraically closed field)という。

  • 定理 1
    Kが代数閉体で、fが f(x) = x^{n} + a_1 x^{n-1} + ... + a_n
     a_1, ..., a_n \in Kの形である場合、
     \alpha_1, ..., \alpha_n \in Kが存在し、 f(x) = (x-\alpha_1)...(x-\alpha_n)である。

  • 拡大体のゆるい定義 2
    体Kにいくつかの元を添加して得られたものLがまた体になっている時、Lを拡大体と呼ぶ。

体Kにn個の元 \alpha_1, ..., \alpha_nを追加して拡大体Lをつくった時、
LはKのn次元ベクトル空間とみなせる。 このベクトル空間の次元を[L : K]の記号で表す。

多項式 f(x) = x^{n} + a_1 x^{n-1} + ... + a_nが考えている対象(体や環など)の多項式の範囲内で、
それ以上因数分解できない時、既約多項式と呼ぶ。

  • 定理2
    Kを体、f(x)をK上既約な多項式 \deg f(x)=nである時、
    L= K[x]/(f(x))は体となり、[L : K] = nである。

ここでK[x]はxの1変数多項式を表し、K[x]/(f(x))は、
K[x]をf(x)=0の範囲で同一とみなした商体を表す。

  • 定義4
    有理数体Qを有限次拡大したものを代数拡大と呼ぶ。

  • 定理3 L/Kを体の代数拡大で \alpha \in Lとする。K上の多項式 f(x) \ne 0 f(\alpha) = 0となり、
     deg f(x)が最小のものは既約であり、定数倍を除いて一意的に定まる。

  • 定義5
    定理3で最上位次数の係数が1のものを最小多項式と呼ぶ。

  • 定義6
    Kを体とする。
    L/Kが代数拡大であり、Lが代数閉体である時、LをKの代数閉包(algebraic closure)と呼ぶ。
    Kの閉包を \overline {K}という記号で表す。

  • 定義7
    (1)  f(x) \in K[x], \alpha \in \overline {K}でf(x)が \overline {K} [x]で (x-\alpha)^{2}で割り切れる時、 \alphaをf(x)の重根と呼ぶ。
    (2)  f(x) \in K[x] \overline {K}で重根を持たない時、分離多項式と呼ぶ。
    (3)  \alpha \in \overline {K}のK上の最小多項式が分離多項式である時、 \alphaはK上分離的(separable)と呼ぶ。

  • 定義8
    A, Bを体Kの拡大体とする。AからBへの準同型写像全体の集合を Hom_K^{al} (A, B)という記号で表す。

  • 定理4
    L/Kを体の代数拡大、 L = K(\alpha) (\alpha \in L)とする。
     \alphaがK上分離的なら、 \# Hom_K^{al} (L, \overline {K}) = [L : K] が成り立つ。 ここで#は準同型写像の数を表す。

定理2と定理4を使い、
Kを体、f(x)をK上既約な多項式として、体L= K[x]/(f(x))をつくる。
 f(x) = (x-\alpha_1)...(x-\alpha_n)として、
 \alpha_1, ..., \alpha_nが分離的であれば、
 \# Hom_K^{al} (K[x]/(f(x)), K[x]) = deg(f) が成り立つ。

代数学2 環と体とガロア理論

代数学2 環と体とガロア理論

楕円曲線の自己準同型

有限体  F_p 上の楕円曲線 y^{2} = x^{3} + a x^{2} + b x + c 上の有理点(x, y)を考える。
x座標,y座標はともに0以上p(素数)未満の整数。

2つの点に対する加法を以下で定義すると、この点と加法は群をなすことが知られている。
これを点の加法と呼ぶことにする。

楕円関数の加法公式 - Pebble Coding

ここで一旦、楕円曲線を離れて、群における以下の概念を確認してみる。

G, H を群、 +_Gを群Gにおける加法、 +_Hを群Hにおける加法とする。
このとき、群Gの元a, bから群Hの元への写像 f: G \to Hが以下の関係を満たす時、写像fを準同型写像(homomorphism)という。
 f(a +_G b) = f(a) +_H f(b)

G, Hが同じ群で、加法 +_G,  +_Hも同じ演算であるときは、写像fを自己準同型写像(endomorphism)という。

楕円曲線に戻る。

楕円曲線Eの元P(x, y)から楕円曲線E'の元P'(x', y')への写像fがx,yの有理式で与えられかつ、
f(O) = Oであるとき、fを同種写像(isogeny)と呼ぶ。

楕円曲線Eから楕円曲線Fへの同種写像 fは、準同型写像であることが知られている。つまり、
 f(P +_E Q) = f(P) +_F f(Q) ここで、 +_E楕円曲線Eでの点の加法、 +_F楕円曲線Fでの点の加法を表す。

楕円曲線EからEへの同種写像は自己準同型写像となる。

すべての楕円曲線は各整数nに対して、n倍写像という自己準同型写像を持つ。
ほとんどの楕円曲線においては自己準同型写像はn倍写像だけである。
n倍写像以外に自己準同型写像を持つタイプの楕円曲線虚数乗法を持つという。

同種写像(isogeny)

楕円曲線Eの元P(x, y)から楕円曲線Fの元Q(X, Y)への写像fがx,yの有理式で与えられるとはどういうことか。

楕円曲線E  y^{2} = x^{3} + a x + bを考える。
点P(x,y)を点Q(X,Y)へ写す写像が、例えば、

 X = \frac {x^{5} + 3 x y + 3} {x^{4} y^{3} + x^{2} y + 2}
 Y = \frac {x^{3} y^{3} + 14 y + 2} {x^{7} y^{6} + x^{6} y^{3} + 89}
のようなものを考えるということである。
ただし、x, y は楕円曲線E上の点であるから、条件が与えられ、X, Y も楕円曲線F上の点であるから、
形としてはかなり限定されるであろうことが想像できる。

まず、yの2乗は x^{3} + a x + bで置き換えられるから、
xの次数の上限をなしとすれば、分母も分子もyは最大でも1次まで考えればよいことが分かる。
X, Y の式をR(x, y)で表すことにすると、一般に
 R(x, y) = \frac {p(x) + q(x) y} {r(x) + s(x) y}と書けることになる。
ここで、分母、分子に {r(x) - s(x)} {y}を掛けると、分母に出てくるyは全て2乗になるからこれもxの式で置き換えられる。
分子に出てくるyの2乗もxの式で置き換えられるから、結局、
 R(x, y) = \frac {p(x) + q(x) y} {r(x)}でよいことが分かる。

ここで、楕円曲線Eから楕円曲線Fへの同種写像は、準同型写像であるという定理を利用する。(証明はせずに使う。)
f(P) + f(-P) = f(O) = O
これは、楕円曲線E上の点Pが点Qへ写されるなら、点-Pは点-Qへ移されることを示している。

楕円曲線F上の点Qを (R_x(x, y), R_y(x,y))と書くと、
点-Qは点-Pを写したものであるから (R_x(x, -y), R_y(x, -y))と表せる。
点Qと点-Qのx座標は等しく、y座標はマイナス倍に等しいことから、
 R_x(x, y) = R_x(x, -y)
 R_y(x, y) = - R_y(x, -y)
でなければならないので、結局、
 R_x(x, y) = \frac {p(x)} {r(x)}
 R_y(x, y) = \frac {p(x) y} {r(x)}
の形であることが分かる。

Elliptic Curves: Number Theory and Cryptography, Second Edition (Discrete Mathematics and Its Applications)

Elliptic Curves: Number Theory and Cryptography, Second Edition (Discrete Mathematics and Its Applications)

数学英単語

数学書に出てくる英単語がわかりずらいので、リストしておく。

homomorphism 準同型
endomorphism 自己準同型

isomorphism 同型
automorphism 自己同型

morphism 有理写像

injective 単射 (行き先が被らない関数)
surjective 全射 (行き先を全て埋め尽くす関数)
bijective 全単射

closure 閉包
associativity 結合性(結合法則)

field 体
group 群
ring 環

threorem 定理
proposition 命題
lemma 補題
corollary 系
conjecture 予想

isogeny 同種 同種 (数学) - Wikipedia
singular 特異
composition 合成
genus 種数 (0は球面, 1はトーラス)
characterictic 標数
separable 分離

swiftとアセンブラ

swiftコードがどのようにアセンブラに出力されているのかをみてみましょう。
Xcodeのプロジェクトで、コマンドラインプロジェクトを生成し、以下のソースをmain.swiftに書き込みます。

import Foundation

func plus(_ a: Int64, _ b: Int64) -> (Int64)
{
    return a + b
}

let r = plus(3, 7)

print("\(r)")

Xcodeの Debug - Debug Workflow - Always Show Disassembly にチェックをつけます。

return a + b

の行にbreakpointを設定して実行してみましょう。

aaa`plus(_:_:):
    0x100001e60 <+0>:  pushq  %rbp
    0x100001e61 <+1>:  movq   %rsp, %rbp
    0x100001e64 <+4>:  movq   %rdi, -0x8(%rbp)
    0x100001e68 <+8>:  movq   %rsi, -0x10(%rbp)
->  0x100001e6c <+12>: addq   %rsi, %rdi
    0x100001e6f <+15>: seto   %al
    0x100001e72 <+18>: movq   %rdi, -0x18(%rbp)
    0x100001e76 <+22>: movb   %al, -0x19(%rbp)
    0x100001e79 <+25>: jo     0x100001e81               ; <+33> at main.swift:13
    0x100001e7b <+27>: movq   -0x18(%rbp), %rax
    0x100001e7f <+31>: popq   %rbp
    0x100001e80 <+32>: retq   
    0x100001e81 <+33>: ud2 

push %rbp
move %rsp, %rbp
は関数の先頭なので、必ずこの2行が入ります。
movq %rdi, -0x8(%rbp)
の行は第1引数の値を第2引数で指定した位置にコピーします。
movq のqは8バイト分(64bit)分のコピーを意味します。
このコマンドは%rsiレジスタの値をレジスタ%rbpが指すアドレスの8バイトマイナス方向の位置にコピーすることを意味しています。

%rbpがスタックの位置を表しており、マイナス方向がpush、プラス方向がpopです。
マイナス方向が上、プラス方向が下とイメージしておくと、スタックのイメージと合います。

ここでレジスタの値をみるには、(lldb)のところに、register read と入れます。

(lldb) register read
General Purpose Registers:
       rax = 0x0000000000000007
       rbx = 0x0000000000000000
       rcx = 0x0000000000000003
       rdx = 0x0000000000000007
       rdi = 0x0000000000000003
       rsi = 0x0000000000000007
       rbp = 0x00007ffeefbff4f0
       rsp = 0x00007ffeefbff4f0
        r8 = 0x0000000000000000
        r9 = 0x000000000007b857
       r10 = 0x00007fff944ee0c8  atexit_mutex + 24
       r11 = 0x00007fff944ee0d0  atexit_mutex + 32
       r12 = 0x0000000000000000
       r13 = 0x0000000000000000
       r14 = 0x0000000000000000
       r15 = 0x0000000000000000
       rip = 0x0000000100001e6c  aaa`aaa.plus(Swift.Int64, Swift.Int64) -> Swift.Int64 + 12 at main.swift:13
    rflags = 0x0000000000000206
        cs = 0x000000000000002b
        fs = 0x0000000000000000
        gs = 0x0000000000000000

(lldb) 

関数の第一引数の値はrdiレジスタ、第二引数の値はrsiレジスタに入ります。
rdiには3、rsiには7が入っていることが分かります。
レジスタにはサイズがあり、レジスタ名の先頭がrは64ビット、先頭eが32ビットのような感じになっていますが、
それ以外は以下を参照して下さい。

x64 Architecture | Microsoft Docs

https://ja.wikibooks.org/wiki/X86アセンブラ/x86アーキテクチャ

addqは右のレジスタに入っている値に左のレジスタに入っている値を加えます。
qは64bit演算であることを意味しています。
seto %al
はオーバーフローが発生していたら%alに1、発生していなければ0を設定します。
%alは8bitレジスタです。

joはオーバーフローが発生していたら指定アドレスに処理をジャンプします。
movq -0x18(%rbp), %rax
によって、plus関数の結果をraxレジスタにセットしています。
戻り値が一つの場合raxレジスタに値をセットして、関数の呼び元に値を伝えます。
popq %rbp
retq
は関数の終わりは必ずこの形になり、callqで呼び出した元の処理に戻ります。
ここでpopq %bpの行にプレークポイントを設定して、デバッグ続行してみましょう。
ここでもう一度レジスタの値を確認します。

(lldb) register read
General Purpose Registers:
       rax = 0x000000000000000a
       rbx = 0x0000000000000000
       rcx = 0x0000000000000003
       rdx = 0x0000000000000007
       rdi = 0x000000000000000a
       rsi = 0x0000000000000007
       rbp = 0x00007ffeefbff4f0
       rsp = 0x00007ffeefbff4f0
        r8 = 0x0000000000000000
        r9 = 0x000000000007b857
       r10 = 0x00007fff944ee0c8  atexit_mutex + 24
       r11 = 0x00007fff944ee0d0  atexit_mutex + 32
       r12 = 0x0000000000000000
       r13 = 0x0000000000000000
       r14 = 0x0000000000000000
       r15 = 0x0000000000000000
       rip = 0x0000000100001e7f  aaa`aaa.plus(Swift.Int64, Swift.Int64) -> Swift.Int64 + 31 at main.swift:13
    rflags = 0x0000000000000206
        cs = 0x000000000000002b
        fs = 0x0000000000000000
        gs = 0x0000000000000000

raxレジスタに3+7の結果である10 = 0xaが入っていることが分かります。
以外にアセンブラも読めるものであることが分かったのではないでしょうか。

戻り値が2つ以上のtupleの場合

plus関数の戻り値が(Int64, Int64)のようなタプルの場合には、戻り値がrax, rdxに入ります。

その他コマンド

leaq メモリ上の場所のアドレス値をレジスタに格納するもの

lealについて - suu-g's diary

Assembly Register Calling Convention Tutorial

ラグランジュの定理

ラグランジュの定理を解説します。
ここでは有限群のみを考慮対象とします。

まず、群の定義です。

有限個の元からなる集合Gを考えます。
集合Gから2つの元 g_1, g_2を選び、 g_1に対して g_2を作用させて結果rを得るという操作(演算)を定義します。
この演算をここでは +で表し、 g_1 + g_2 = rと書きます。

1) 集合Gからどの2つの元 g_1, g_2を選んでも演算結果 g_1 + g_2がGに含まれる。
2) (単位元0の存在) 集合Gからどの元gを選んでも g + 0 = 0 + g = gとなる単位元0が存在しGに含まれる。
3) (逆元 -gの存在) 集合Gからどの元gを選んでも g + (-g) = (-g) + g = 0となる逆元 -gが存在しGに含まれる。
4) (結合法則) 集合Gから選んだどの元 g_1, g_2, g_3に対しても、 g_1 + ( g_2 + g_3 ) = (g_1 + g_2) + g_3が成立つ。

この条件はとても厳しいものです。

例:
例えば集合Gを整数の0, 1, 2とし演算を整数の足し算と考えると、1+2=3ですから、集合Gをはみ出してしまい、群にはなりません。
次に集合Gを整数の0,1,2 とし演算を整数の足し算した後3で割って余りをとると考えると、演算結果は全てGに収まり、
全ての元に単位元、逆元が存在し、結合法則も成り立つので群になります。

さらに部分群も定義しておきます。
部分群Hの定義は、群Gの元を有限個取り出して、集合Hを作り、群Gと同じ演算を使った時に集合Hがまた群の性質を満す場合の元の集まりです。
この条件もとても厳しいものです。

そして、群と部分群に対しては、以下のラグランジュの定理が成りたちます。

ラグランジュの定理: 群Gの元の個数はその部分群Hの個数で割り切れる。

ここでは直感的に理解しやすいものだけを述べています。

証明のイメージは以下のようなものです。
部分群Hの元を次のように表します。 h_1, h_2, ..., h_j
この元は全て群Gの元でもあります。
この元の集まりに対して、Gの元 g_1を持って来て加算します。
 h_1 + g_1, h_2 + g_1, ..., h_j + g_1
これらは群Gの元にGの元を演算したものですから、群Gの法則1)により必ずGの元になります。
これらは群Gのうちで全て異なる元になります。
なぜかというと、例えば、 h_1 + g_1 h_2 + g_1が同じ元であったとすると、
群Gの法則3)によって g_1には逆元が必ず存在しますから、 (h_1 + g_1) + (-g_1) = (h_2 + g_1) + (-g_1)が成りたちます。
群Gの法則4)によってこれは h_1 + (g_1 + (-g_1)) = h_2 + (g_1 + (-g_1))となり、
 h_1 + 0_g = h_2 + 0_gが成り立ちます。
この 0_gは群Gの単位元ですが、演算規則は群Gと群Hで同じなので、群Hの単位元 0_hに一致します。
そして h_1 = h_2となりますが、これは群Hの異なる元を選んだことに矛盾します。
これで、 h_1 + g_1, h_2 + g_1, ..., h_j + g_1は全て異なる元であることが言えました。

ここで、このように作った h_1 + g_1, h_2 + g_1, ..., h_j + g_1 = H1ですが、 g_1とはまた別の群Gの元 g_2を持って来て、
 h_1 + g_2, h_2 + g_2, ..., h_j + g_2 = H2を作ります。
同じ議論でこれらも元が全て異なり、群Gの元となります。
H2の個数はH1と同じですね。
これを繰り返して、
H1, H2, ...を考えます。
H1, H2, ..., Hn のように繰り返していくと、この元を全て集めたものはGと一致することが言えます。
理屈はこうです。
H1, H2, ... Hnは群Gの元からはみ出すことはありません。(群Gの法則1による)
また、仮にどうやっても群Gの元vが作れなかったととしましょう。
その場合、 h_1 + v, h_2 + v, ..., h_j + vを作ります。
 h_1, h_2, ... h_jは部分群Hですから、単位元 0_hが含まれるはずです。
この単位元は群Gの単位元でもありますから、
これらのうち、かならずどれかは 0_h + v = vになるので、H1, H2, ...を作っていくと、必ず群Gの元全てを網羅できることが分かります。

分かったことは、
「H1, H2, ..., Hnで群Gの元全てを生み出すことができる。」
「H1, H2, ..., Hnに含まれる元の数は同じで各Hjに元の重複はない」
これから、群Gの元の個数は部分群Hの元の個数で割り切れることが言えます。

ラグランジュの定理の強力さ

群と部分群の定義はかなり厳しいものですが、必要な最低限の条件しか課していません。
また抽象度が高いお陰で、いくら演算が複雑で元の数が多かったとしても、群とその部分群の条件を満たすことが確認できさえすれば、
この定理が応用できるというのが魅力です。

約数という概念が出てくることから、群の元の個数を素数に関連付けたらさらにいろいろ定理が出て来そうな感じがしますよね。

参考:

以下のYouTubeの解説もちょっとおもしろかったです。

【全8回】第6回「ラグランジュの定理」~部分群と位数の関係~【フェルマーの小定理と群論】 - YouTube

http://www.nurs.or.jp/~lionfan/group3.pdf