計算機科学のブログ

有限体上の除算 素数、フェルマーの小定理、べき演算の再定義、負の整数にも対応、Goでコーディング

プログラミング・ビットコイン ―ゼロからビットコインをプログラムする方法 (Jimmy Song(著)、中川 卓俊(監修)、住田 和則(監修)、中村 昭雄(監修)、星野 靖子(翻訳)、オライリー・ジャパン)の1章(有限体)、1.7(有限体上の除算)の練習問題8、9の解答をPythonではなくGoで求めてみる。

8

3 24 = 3 · 2 4 31 - 2 = 3 · 2 4 29 = 4
1 7 - 3 = 1 7 - 3 · 1 7 31 - 1 = 1 7 27 = 29
4 - 4 · 11 = 4 31 - 1 · 4 - 4 · 11 = 4 26 · 11 = 13

最終計算には計算機を使用。

9

コード

ecc.go

// Package ecc (Elliptic Curve Cryptography, 楕円曲線暗号)
package ecc

import "fmt"

// FieldElement 有限体の要素
type FieldElement struct {
	Num   int
	Prime int
}

func (fe FieldElement) String() string {
	return fmt.Sprintf("FieldElement_%v(%v)", fe.Prime, fe.Num)
}

// NewFieldElement ...
func NewFieldElement(n, p int) (FieldElement, error) {
	if n >= p || n < 0 {
		return FieldElement{},
			fmt.Errorf("%v not in field range 0 to %v", n, p-1)
	}
	return FieldElement{n, p}, nil
}

// Eq ...
func Eq(fe1, fe2 FieldElement) bool {
	if fe1.Prime == 0 || fe2.Prime == 0 {
		return false
	}
	return fe1.Num == fe2.Num && fe1.Prime == fe2.Prime
}

// Ne ...
func Ne(fe1, fe2 FieldElement) bool {
	return !Eq(fe1, fe2)
}

// Add ...
func Add(fe1, fe2 FieldElement) (FieldElement, error) {
	if fe1.Prime != fe2.Prime {
		return FieldElement{}, fmt.Errorf("Cannot add two numbers in diferent Fields")
	}
	return FieldElement{Num: (fe1.Num + fe2.Num) % fe1.Prime, Prime: fe1.Prime}, nil
}

// Sub ...
func Sub(fe1, fe2 FieldElement) (FieldElement, error) {
	if fe1.Prime != fe2.Prime {
		return FieldElement{}, fmt.Errorf("Cannot sub two numbers in diferent Fields")
	}
	num := (fe1.Num - fe2.Num) % fe1.Prime
	if num < 0 {
		num += fe1.Prime
	}
	return FieldElement{Num: num, Prime: fe1.Prime}, nil
}

// Mul ...
func Mul(fe1, fe2 FieldElement) (FieldElement, error) {
	if fe1.Prime != fe2.Prime {
		return FieldElement{},
			fmt.Errorf("Cannot mul two numbers in different Fields")
	}
	if fe1.Num == 0 {
		return fe1, nil
	}
	if fe2.Num == 0 {
		return fe2, nil
	}
	fe := fe1
	for i := 1; i < fe2.Num; i++ {
		fe, _ = Add(fe, fe1)
	}
	return fe, nil
}

// Div ...
func Div(fe1, fe2 FieldElement) (FieldElement, error) {
	if fe1.Prime != fe2.Prime {
		return FieldElement{},
			fmt.Errorf("Cannot div two numbers in diffrerent Fields")
	}
	if fe2.Num == 0 {
		return FieldElement{},
			fmt.Errorf("division by zero")
	}
	return Mul(fe1, Pow(fe2, fe2.Prime-2))
}

// Pow ...
func Pow(fe FieldElement, n int) FieldElement {
	if n < 0 {
		n += fe.Prime - 1
	}
	if n == 0 {
		t, _ := NewFieldElement(0, fe.Prime)
		return t
	}
	t := fe
	for i := 1; i < n; i++ {
		t, _ = Mul(t, fe)
	}
	return t
}

ecc_test.go

package ecc

import "testing"

func TestNewFieldElementEq(t *testing.T) {
	a, _ := NewFieldElement(7, 13)
	b, _ := NewFieldElement(6, 13)
	got := Eq(a, b)
	if got {
		t.Errorf("Eq(%v, %v) got %v, want false", a, b, got)
	}
	got = Eq(a, a)
	if !got {
		t.Errorf("Eq(%v, %v) got %v, want true", a, a, got)
	}
}
func TestNewFieldElementNe(t *testing.T) {
	a, _ := NewFieldElement(7, 13)
	b, _ := NewFieldElement(6, 13)
	got := Ne(a, b)
	if !got {
		t.Errorf("Ne(%v, %v) got %v, want true", a, b, got)
	}
	got = Ne(a, a)
	if got {
		t.Errorf("Ne(%v, %v) got %v, want false", a, a, got)
	}
}

func TestAdd(t *testing.T) {
	a, _ := NewFieldElement(7, 13)
	b, _ := NewFieldElement(12, 13)
	c, _ := NewFieldElement(6, 13)
	d, _ := Add(a, b)
	if Ne(d, c) {
		t.Errorf("Add(%v, %v) got %v, want %v", a, b, d, c)
	}
}

func TestSub(t *testing.T) {
	prime := 19
	tests := []struct {
		nums    []int
		wantNum int
	}{
		{[]int{11, 9}, 2},
		{[]int{6, 13}, 12},
	}
	for _, test := range tests {
		a, _ := NewFieldElement(test.nums[0], prime)
		b, _ := NewFieldElement(test.nums[1], prime)
		want, _ := NewFieldElement(test.wantNum, prime)
		got, _ := Sub(a, b)
		if Ne(got, want) {
			t.Errorf("Sub(%v, %v) got %v, want %v", a, b, got, want)
		}
	}
}

func TestMul(t *testing.T) {
	p := 13
	a, _ := NewFieldElement(3, p)
	b, _ := NewFieldElement(12, p)
	got, _ := Mul(a, b)
	want, _ := NewFieldElement(10, p)
	if Ne(got, want) {
		t.Errorf("Mul(%v, %v) got %v, want %v", a, b, got, want)
	}
}

func TestDiv(t *testing.T) {
	prime := 19
	tests := []struct {
		num, den, want int
	}{
		{2, 7, 3},
		{7, 5, 9},
	}
	for _, test := range tests {
		num, _ := NewFieldElement(test.num, prime)
		den, _ := NewFieldElement(test.den, prime)
		got, _ := Div(num, den)
		want, _ := NewFieldElement(test.want, prime)
		if Ne(got, want) {
			t.Errorf("Div(%v, %v) got %v, want %v", num, den, got, want)
		}
	}
}
func TestPow(t *testing.T) {
	prime := 13
	tests := []struct {
		n, p, want int
	}{
		{3, 3, 1},
		{7, -3, 8},
	}
	for _, test := range tests {
		a, _ := NewFieldElement(test.n, prime)
		got := Pow(a, test.p)
		want, _ := NewFieldElement(test.want, prime)
		if Ne(got, want) {
			t.Errorf("Pow(%v, %v) got %v, want %v", a, test.p, got, want)
		}
	}
}

入出力結果

% go test
--- FAIL: TestPow (0.00s)
    ecc_test.go:83: Pow(FieldElement_13(7), -3) got FieldElement_13(7), want FieldElement_13(8)
FAIL
exit status 1
FAIL	bitcoin/ecc	0.496s
% go test
PASS
ok  	bitcoin/ecc	0.427s
 % go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:82:13: undefined: Div
FAIL	bitcoin/ecc [build failed]
% go test
PASS
ok  	bitcoin/ecc	0.062s
% go test -v
=== RUN   TestNewFieldElementEq
--- PASS: TestNewFieldElementEq (0.00s)
=== RUN   TestNewFieldElementNe
--- PASS: TestNewFieldElementNe (0.00s)
=== RUN   TestAdd
--- PASS: TestAdd (0.00s)
=== RUN   TestSub
--- PASS: TestSub (0.00s)
=== RUN   TestMul
--- PASS: TestMul (0.00s)
=== RUN   TestDiv
--- PASS: TestDiv (0.00s)
=== RUN   TestPow
--- PASS: TestPow (0.00s)
PASS
ok  	bitcoin/ecc	0.466s
%