【Goで実装】ビットコイン・プログラミング解説 数学基礎1 有限体
こちらの本を参考にビットコインについてお勉強していきます。
Go言語で実装してながら学んでいきたいと思います。環境は以下です。
go version go1.20.6 darwin/arm64
プチロードマップ
書籍の目次をなぞっているだけですが...。書籍では、Pay-to-script-hash, ブロック, ネットワーキング, SPV, ブルームフィルター...と続いていきますが、一旦上記までを学んでいきたいと思います。
有限体
早速ですが、数学の基礎のところです。有限体からいきます。
限られたの数の集合を有限体、と呼びます。
例えば、個数を表す
0〜9までの数字の集まりですね。シンプルです。
これを一般的にすると以下です。
有限体が楕円曲線暗号に利用されるようなのですが、今のところ、どのようにつながっていくのかさっぱりわかりません。
有限体の位数は素数
先ほどの例では位数10の有限体を見ました。でも、この位数は素数じゃないといけないんです。
素数は、数えると落ち着く、あれですね（ジョジョネタで、わからない方すみません）。
とくにかけ算(乗算)と割り算（除算）のところで、素数じゃないといけないということがわかります。それでは実装していきます。
有限体の要素の実装
有限体の"要素"を表すFieldElementというクラスです。全体ではなく、要素、というのがポイントですね。位数11の有限体の数のなかの"1"など1つの要素を表します。
type FieldElement struct {
num int
prime int
}
func NewFieldElement(num int, prime int) FieldElement {
if num >= prime || num < 0 {
log.Panicf("Num %d not in field range 0 to %d", num, prime-1)
}
return FieldElement{num, prime}
}
func (fe *FieldElement) String() string {
return fmt.Sprintf("FieldElement_%d(%d)", fe.prime, fe.num)
}
動かしてみます。
a := NewFieldElement(1, 11)
fmt.Printf("位数11の有限体の\"1\": %+v", a) // 位数11の有限体の"1": {num:1 prime:11}
有限体の加算と減算
有限体の足し算や引き算には、割り算のあまりを求める(モジュロ演算)を使います。
有限体のある要素同士をふつうに足し算すると、有限体にはない数になる場合があります。
例えば、 5 と 7 を普通に足すと、 12 になっちゃいます。
でも、この有限体のなかに 12 という数はない...。
そこで、モジュロ演算を使うことで、足し算を可能にします。有限体のある要素とある要素を足した結果も、有限体に含まれるようにするため、足し算の方法をちょっと変えよう、ということです。
5 と 7 の加算の結果は 1 になります。
図で表すとこんな感じです。
・・・
時計を例に考えてみます。時間の"分"だけを考えると
0分, 1分, 2分, ... 59分
たとえば、今、n時50分だとして、20分後は、何分でしょうか？
☞ 答え: 10分
これは以下の計算と同じです。50と20を足すと70になるけど、それを60で割ったあまりは10になります。
・・・
これをかっこよく定義すると以下になります。
急に難しくなった気がしますが、言ってることは時計の例とおなじです。
まず、p個の要素がある有限体に a と b という要素があります。
そして、a に b を有限体の足し算で足した答え = a + b を p で割ったあまり、ということです。
このように、計算した結果も有限体のいずれかの要素になることを、「閉じている」と言います。
減算の場合
引き算でも同様に求めることができます。
たとえば、今、n時10分だとして、20分前は何分でしょうか？
☞ 答え: 50分
マイナスの余りを求めるのって直観的じゃないですよね...。10 - 20は-10になるので、その-10を60で割った余りって、、、何ですか？...という感じです。ですが、式に当てはめるとわかりやすいようです。
余りは常にプラスになるので、商は整数なので-1となり、余りは50に決まるみたいです。うーん、直感的じゃない...と思うのは自分だけでしょうか。でも、時計の例と照らし合わせると、あってるので、そういうことにしましょう。
有限体の加算・減算の実装
それでは実装していきます。
// 有限体の加算
func (fe *FieldElement) Add(other *FieldElement) FieldElement {
if fe.prime != other.prime {
log.Panicf("Cannot add two numbers in different Fields")
}
num := (fe.num + other.num) % fe.prime
return FieldElement{num, fe.prime}
}
// 有限体の減算
func (fe *FieldElement) Sub(other *FieldElement) FieldElement {
if fe.prime != other.prime {
log.Panicf("Cannot sub two numbers in different Fields")
}
num := modLikePython(fe.num-other.num, fe.prime)
return FieldElement{num, fe.prime}
}
// Goの場合、モジュロ演算するとマイナスになっちゃうので、Pythonのように正の値になるように調整する
// https://stackoverflow.com/a/43018347
func modLikePython(d int, m int) int {
var res int = d % m
if (res < 0 && m > 0) || (res > 0 && m < 0) {
return res + m
}
return res
}
注意点は参考書籍で使用しているPythonと、ここで使用しているGoでは、マイナスの場合にモジュロ演算の結果が異なる、という点です。それを調整するために modLikePython という関数を用意しました。
a := NewFieldElement(40, 60)
b := NewFieldElement(50, 60)
fmt.Printf("足し算: %+v\n", a.Add(&b)) // 足し算: {num:30 prime:60}
fmt.Printf("引き算: %+v\n", a.Sub(&b)) // 引き算: {num:50 prime:60}
動いてそうです。
有限体の乗算
かけ算です。かけ算は足し算の繰り返しなので、シンプルです。
早速、実装を見てみましょう。
// 有限体の乗算
func (fe *FieldElement) Mul(other *FieldElement) FieldElement {
if fe.prime != other.prime {
log.Panicf("Cannot mul two numbers in different Fields")
}
num := (fe.num * other.num) % fe.prime
return FieldElement{num, fe.prime}
}
確認します。
a := NewFieldElement(3, 13)
b := NewFieldElement(12, 13)
c := NewFieldElement(10, 13)
// (3 * 12) % 13 = 10
fmt.Printf("%+v\n", reflect.DeepEqual(a.Mul(&b), c)) // true
OKです。
ところで、有限体の乗算に関連して、ひとつ面白い性質があります。
1,3,7,13,18をそれぞれの要素にかけ算（もちろん有限体のかけ算）してみた結果です。
一番上の
位数が素数であることで、有限体のすべての要素は対等になります。
と表現しています。へー！😳
べき乗
べき乗の場合です。なんかイマイチな気がしますが以下にしました。
// 有限体のべき乗
func (fe *FieldElement) Pow(exponent int) FieldElement {
num := (int(math.Pow(float64(fe.num), float64(exponent)))) % fe.prime
return FieldElement{num, fe.prime}
}
a2 := NewFieldElement(3, 13)
b2 := NewFieldElement(1, 13)
// 3^3 % 13 = 1 (27 ÷ 13 なので)
fmt.Printf("%+v\n", reflect.DeepEqual(a2.Pow(3), b2)) // true
すみません、intのmax値は2147483647なのですぐオーバーフローを起こしてしまい、ダメでした...
後述する除算の計算ではすごく大きい値がでてくるので、そこで失敗するケースが出てきました。
調べてみるとなんと、Expという関数が用意されているではありませんか...！これをそのまま使います。
// 有限体のべき乗
func (fe *FieldElement) Pow(exponent int) FieldElement {
num := pow(fe.num, exponent, &fe.prime)
return FieldElement{num, fe.prime}
}
// PythonのPowの第三引数の挙動を再現する
// https://stackoverflow.com/a/77542076
func pow(a, b int, m *int) int {
var mod *big.Int
if m != nil {
mod = big.NewInt(int64(*m))
}
result := new(big.Int).Exp(
big.NewInt(int64(a)),
big.NewInt(int64(b)),
mod,
)
return int(result.Uint64())
}
この関数はべき乗がマイナスの場合にも対応している優れものです。ありがたや...
有限体の除算
ここは個人的に理解するのにかなり苦しみました。
フェルマーの小定理、というのを使う必要があります。
日本語で書くと、
気を付けたいのは、素数でのみ、常に真となります。素数が前提になってます。
だから素数って重宝されるんでしょうか...？人類はすごい武器を手に入れましたね。
この小定理の導き方は調べて理解できる方は理解してください。自分はわかりませんでした。
とりあえず、素数が位数の有限体では、これが使える、ということを覚えます。
・・・
本題の割り算に入ります。割り算はかけ算の逆なので...
小さい
ここの
☝️ まず、あえて1をかけてます。
☝️
☝️ 最後に、指数部分の
すなわち：
なので
これの意味は、有限体の割り算は、べき乗に変換できる、ということです！
よく例で出てくる、
この有限体の中では常に、すべての
実際に割り算してみましょう。
見事に割り算がべき乗の計算に変換されています！すごい。それでは実装します。
有限体の除算の実装
先ほど定義したpow関数を利用します。
// 有限体の除算
func (fe *FieldElement) Div(other *FieldElement) FieldElement {
if fe.prime != other.prime {
log.Panicf("Cannot div two numbers in different Fields")
}
num := fe.num * pow(other.num, fe.prime-2, &fe.prime) % fe.prime
return FieldElement{num, fe.prime}
}
動かしてみます。
a := NewFieldElement(3, 31)
b := NewFieldElement(24, 31)
c := NewFieldElement(4, 31)
fmt.Printf("%v\n", reflect.DeepEqual(a.Div(&b), c)) // true
第1回目は以上です！
お疲れ様でした。
Discussion