Pebble Coding

プログラマーの作業メモ

数学英単語

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

homomorphism 準同型
endomorphism 自己準同型

isomorphism 同型
automorphism 自己同型

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

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

field 体
group 群
ring 環

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

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

準同型写像に関する元の数についての定理

準同型写像に関する元の数についての定理を直観的に理解したいと思います。

G,Yを有限群とする。
群Gから群Yへの準同型写像(Homomorphism)を  \phi とする。
すなわち、 g_1, g_2 をGの任意の元として、
 \phi(g_1 + g_2) = \phi(g_1) + \phi(g_2) が成りたちます。
ここで左辺のプラス +は群Gでの演算,右辺のプラス +は群Yでの演算です。

 \phi の核は  Ker(\phi) = \{  g \in G | \phi(g) = 0 \}
で定義されます。
核とは、写像の行く先の元が全て群Yの単位元0になる群Gの元の集まりのことです。
 \phi の全ての行く先の元を全て集めたものは、一般に、Yの部分群となることが知られています。
(ここでは証明しません。)

 \phi の像を \phi(G)と書きます。
このとき、以下が成りたちます。
 \#G = (\#Ker(\phi)) (\#\phi(G))
つまり、群Gの元の数は、核 Ker(\phi)の元の数と像 \phi(G)の元の数の積に等しい。

例として、群Gの元の数は20,核 Ker(\phi)の元の数は4だとしましょう。
 g_1, g_2, g_3, g_4が核でGの要素だとします。
この4つの元は \phiによって、Yの単位元0に移されます。すなわち、
 \phi ( g_1 ) = 0
 \phi ( g_2 ) = 0
 \phi ( g_3 ) = 0
 \phi ( g_4 ) = 0
がなりたっています。
そして、準同型性からGの核でない任意の元 g_iに対して以下が成り立ちます。
 \phi ( g_i + g_1 ) = \phi ( g_i ) + \phi ( g_1 )
 \phi ( g_i + g_2 ) = \phi ( g_i ) + \phi ( g_2 )
 \phi ( g_i + g_3 ) = \phi ( g_i ) + \phi ( g_3 )
 \phi ( g_i + g_4 ) = \phi ( g_i ) + \phi ( g_4 )
この右辺の2番目の項は群Yの単位元に等しいです。
Yは群なので、Yの任意の元にYの単位元を加えたものは同じ元のままですね。
するとこの4つの式の右辺は全て同じ \phi(g_i)ということになります。
ということは左辺も全て同じですね。
 \phi ( g_i + g_1 ) = \phi ( g_j )
 \phi ( g_i + g_2 ) = \phi ( g_k )
 \phi ( g_i + g_3 ) = \phi ( g_l )
 \phi ( g_i + g_4 ) = \phi ( g_m )
の4つの像は同じYの元であるということになります。
 g_j, g_k, g_l, g_mが同じ元なのか異なる元なのかは分かりませんが、
 \phi ( G )の元の数は群Gの約数になりそうな雰囲気です。

f:id:pebble8888:20180612222907p:plain

これはイメージ図ですが、 g_1, g_2, g_3, g_4が核の元の数4で、
Gの4個の組みの像が同じYの元になってしまうため、像の元の数が5になっている様子を表しています。
先にイメージだけでも掴んでおくと、この定理を利用する際にとても役に立ちます。
また、この定理の証明は別の文献を参照下さい。
私はこの証明は見つけられていませんが、群論の教科書に載っているのではないかと思います。

この定理では群Yの元の個数については何も言っていません。
仮に、群Yが群Gと同じだった場合、つまり、自己準同型写像(Endomorphism)だった場合は、
さらに色々定理が出てきそうだという想像がつきますが、この記事ではここまでとしておきます。

群論における写像 - Pebble Coding

群の定義といろんな具体例 | 高校数学の美しい物語

準同型写像 [物理のかぎしっぽ]

なお、この定理はこの本のAppendixに載ってました。

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)

楕円曲線の有理点の数の求め方 schoof アルゴリズムその1

 F_p 上の楕円曲線  y^{2} = x^{3} + a x^{2} + b の有理点個数の求め方です。

ここではSchoofアルゴリズムの理解を目的とし、少しづつ理解を進みます。

まず使うのはHasseの定理です。

Hasse-Weilの定理(楕円関数限定版) - Pebble Coding

有理点の数を#Eで表すと、 -2 \sqrt {2} \leq t  \leq 2 \sqrt {2}
 t = p + 1 - \#E
が成り立ちます。
tはある範囲内の唯一つの整数なので、  t \mod N = c を満たす非負整数N,c が見つかったと仮定します。
ここで、
 t = dN + c, c \lt Nなので、 N が 4 \sqrt {2}より大きかった場合は、dは0しかありえず、tはcと求まります。

計算する必要があるのは、 t \mod N, N \lt 4 \sqrt {2}だけとなりましたが、 Nが大きいと計算量が多過ぎるので、 中国の剰余定理を用いて、もう少し分解します。
中国剰余定理の証明と例題(二元の場合) | 高校数学の美しい物語

中国の剰余定理は、2元の場合だけを書くと、  l1 l2 が互いに素なとき
 t = a1 \mod l1
 t = a2 \mod l2
を満たす t が 0 以上  l1 l2 未満の範囲に唯1つ存在する。
というもので、これは任意の元の数に拡張しても成り立ちます。

 l_iをいくつかもってきて全ての積を作ったものをNとします。
 l_iは全て、互いに素な素数とします。
 N = l_1 l_2 ... l_n
 t \mod l_1 = c_1
 t \mod l_2 = c_2
...
 t \mod l_n = c_n
を計算して、あとはユークリッドの互除法を用いてtを計算します。

Schoof's algorithm - Wikipedia

素体を拡大する

素体  F_pを拡大してみます。
 F_3を拡大して、拡大体  F_{{3}^{2}}を作ることにします。
体の拡大には既約多項式を使います。
ここでは、規約多項式 x^{2} + 2 x + 2 = 0を使います。
 F_3を作る場合は素数3で割った余りを使うというルールでした。
 F_3の元は{0, 1, 2}の3つですが、加法の単位元が0で乗法の単位元が1です。

 F_{{3}^{2}}を作る場合のルールは、既約多項式のxを使って、
xを素体に追加して、xを整数1とは独立したものとして計算し、
 x^{2}が出現した場合は  x^{2} = - 2x - 2 = x + 1 に置き換えるというものです。
また1の係数やxの係数は3で割った余りを使います。

元は{0, 1, 2, x, 2x, 1 + x, 1 + 2x, 2 + x, 2 + 2x}の9個になります。
一般に拡大体  F_{{p}^{n}}の元の数は {{p}^{n}}個です。

これらの元同士の加算には x^{2}の項は出てこないため、3で割った余りを使うだけで、簡単なので省略します。
これらの元同士の乗算は面倒なので表にしてみました。

0 1 2 x 2x 1+x 1+2x 2+x 2+2x
0 0 0 0 0 0 0 0 0 0
1 0 1 2 x 2x 1+x 1+2x 2+x 2+2x
2 0 2 1 2x x 2+2x 2+x 1+2x 1+x
x 0 x 2x x+1 2+2x 1+2x 2 1 2+x
2x 0 2x x 2+2x 1+x 2+x 1 2 1+2x
1+x 0 1+x 2+2x 1+2x 2+x 2 2x x 1
1+2x 0 1+2x 2+x 2 1 2x 2+2x 1+x x
2+x 0 2+x 1+2x 1 2 x 1+x 2+2x 2x
2+2x 0 2+2x 1+x 2+x 1+2x 1 x 2x 2

例としてひとつ計算してみます。
 (2x+2) * (2x +2 )= 4 x^{2} + 8x + 4 = x^{2} + 2x + 1 = x + 1 + 2x + 1 = 3x + 2 = 2

ここでは、綺麗に1列に同じ元が出てこないようになっていますね。
既約多項式を使わないと、このようにはならず、列に同じ元が2つ以上出てくるようになってしまいます。

規約多項式 x^{2} + 2 x + 2 = 0以外にも存在します。
例えば、 x^{2} + 1 = 0 x^{2} + x + 1 = 0も規約多項式です。
これを使って掛け算の表を作った場合、異なる表になりますが、元の役割を入れ替えることで、
一つ目の規約多項式を使った場合と同じ表になることが知られているそうです。(同型と言います。)
規約多項式は計算量が少なくなるように係数が小さい方がよいので、
通常 x^{2} + 2 x + 2 = 0などは使いません。

素数が3の時の拡大体  F_{{3}^{2}} を手に入れることができましたが、
素数が3より大きい時に規約多項式をどのように選べば良いでしょうか。
ひとつの例としては、n = p + 1 として、
 x^{n} + 2 x^{n-1} + 2 x^{n-2} + ... + 2 x + 2 = 0を選べば良いです。
これは、アイゼンシュタインの既約判定法を用いて作ったものですが、
係数が小さい方が計算量が少なくてすみますから、通常これは選びません。

最も効率が良い規約多項式を得るには、別の構成方法を用いるようです。

参考:
http://lupus.is.kochi-u.ac.jp/shiota/misc/field/FiniteField.html

体の拡大は、もとの体に規約多項式の解を添加しているとも言えます。

なお、規約多項式 x^{2} + 1 = 0 x^{2} + x + 1 = 0を使った場合は、
この2つの解をそれぞれ、 \alpha, \betaとすると、 (x - \alpha) (x - \beta) = 0なので、
 \alpha \beta = 1が満たされ、 \beta = {\alpha}^{-1}と書けることを覚えておくと、どこかで役にたつかも知れません。

BabyStep GiantStep法(BSGS法)

DLP問題を解くアルゴリズムの一つとしてBabyStep GiantStep法があります。

DLP問題とは、対称群の位数nに対して、生成元をg、群のある元をaとして、
 {g}^{x} = aを満たすxを求める問題です。
ここで、解はただ一つのみ必ず存在することは前提とします。
なので、解が存在するかどうかを調べる必要はありません。
問題はどうやって計算量を少なく求めるかです。

xは{0, 1, 2, ..., n-1}のいずれかです。
xをある数の倍数に小さい数を加えたものとして計算できれば、少ない計算量で求めることができるんじゃね?
ってのがこのアルゴリズムのアイデアです。

まずある数の倍数として適当な値とはどのくらいの大きさかを考えます。
 x = qm + rと表した時、xは最大でn-1なのですから、
mはnの平方根くらいの大きさなら、qとrを小さい方から闇雲に設定した時、xは0からn-1の全てを
最も効率よく網羅できそうですね。
そこでmはnの平方根を整数に切り上げたものに取ることにします。
そしてxをmで割った商をq, 余りをrとします。

 {g}^{qm + r} = a を変形して、
 {{g}^{m}}^q = a {g}^{-r}とします。
この右辺の値を全ての余りのケースについて計算しておきます。
つまり、 a {g}^{0}, a {g}^{-1}, a {g}^{-2}, ..., a {g}^{-m+1}を計算しておきます。
これをベビーステップ集合と言います。

次に左辺をqの小さい方から順番に計算していき、ベビーステップ集合内の値と一致するまで繰り返します。
手順として d = {g}^{m}をまず計算し、 {d}^{1}, {d}^{2}, {d}^{3}, ...のように計算していきます。
これをジャイアントステップ集合と言います。
一致するものが見つかった場合は、
 {d}^{q} = a {g}^{-r}となり、qとrが確定したということですから、
 {g}^{mq} {g}^{r} = aとなるので、x = mq + r と求まります。

大事なのは計算量です。
少なくとも、ベビーステップ集合の計算で、 m = \sqrt n回のかけ算が必ず必要となります。
したがって、このアルゴリズムのオーダーは \sqrt nとなり、 n > {2}^{160} 程度あれば、
ハイパーコンピューターをもってしても解くことは不可能となります。

別の取り方

ベビーステップ集合の取り方は他にもあります。
 {g}^{qm + r} = a を変形して、
 {g}^{r} = {a} {{g}^{-m}}^q とし左辺をベビーステップ集合としてもよいです。