有限体の乗算とべき演算 Goでコーディング
プログラミング・ビットコイン ―ゼロからビットコインをプログラムする方法 (Jimmy Song(著)、中川 卓俊(監修)、住田 和則(監修)、中村 昭雄(監修)、星野 靖子(翻訳)、オライリー・ジャパン)の1章(有限体)、1.6(有限体の乗算とべき演算)の練習問題4、5、1.6.1(Pythonで乗算をコーディング)の練習問題6、1.6.2(Pythonでべき乗をコーディング)の練習問題7の解答をPythonではなくGoで求めてみる。
4
5
すべて同じ集合で、その濃度は有限体と同じ19。
6
コード
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
}
// Pow ...
func Pow(fe FieldElement, n int) FieldElement {
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 TestPow(t *testing.T) {
p := 13
a, _ := NewFieldElement(3, p)
b := 3
got := Pow(a, b)
want, _ := NewFieldElement(1, p)
if Ne(got, want) {
t.Errorf("Pow(%v, %v) got %v, want %v", a, b, got, want)
}
}
入出力結果
% go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:63:12: undefined: Mul
FAIL bitcoin/ecc [build failed]
% go test
PASS
ok bitcoin/ecc 0.237s
% 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)
PASS
ok bitcoin/ecc 0.062s
% go test
PASS
ok bitcoin/ecc 0.271s
% go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:74:12: undefined: Pow
FAIL bitcoin/ecc [build failed]
% go test
PASS
ok bitcoin/ecc 0.217s
%