BTC_有限体

有限体⇒楕円曲線暗号（ECC）⇒署名アルゴリズム、検証アルゴリズム

の順番で学習することで、ビットコインのトランザクションの仕組みがわかりやすくなるらしい。

有限個の数からなる集合と２つの演算（加算と乗算）が以下を満たす

1. 集合内のaとbに対し、a + bも a・b も集合内に存在する。（閉じているという）
2. a+0=a となるような0が存在する（この0を加法単位元という）
3. a・1=aとなるよう1が存在する（この1を乗法単位元という）
4. 集合内のaに対し、a + (-a) = 0 を満たせる -aが集合内に存在する（このaに対する-aを加法逆元という）
5. 集合内の0でないaに対し、a・a**-1 = 1を満たせるa**-1が集合内に存在する（このaに対するa**-1を乗法逆元という）
6. 集合の大きさを位数という

位数をpとする場合、有限体の集合は以下のように表現される

Fp = {0, 1, 2,... p-1}

{}内の数は要素と呼ばれる

例えば、位数11の有限体は以下のようになる

F11 = {0,1,2,3,4,5,6,7,8,9,10,11}

除算で余りの数を求める計算。

モジュロ演算を有限体の中の演算で使用することによって、閉じている有限体を作ることができる

例）7 % 3 = 1

例）-27 % 13 = 12

以下のような有限体があるとする

F19 = {1,2,3,...18}

a,b ∈ F19 (a,bはF19に含まれる)のとき、 閉じている状態の加算は

a +f b ∈ F19

という表現になる（通常の加算と区別するために、有限体上の加算は+fで表す）

モジュロ演算を使用することで、閉じている状態の加算を実現する

a +f b = (a + b) % 19

通常の加算を行ったあとに、位数でモジュロ演算を行うことで閉じた状態になる

加法逆元については以下のように定義される

a ∈ Fp の場合、 -f a ∈ Fp　であり

-f a = (-a) % p となる

F19の場合、

-f 9 = (-9) % 19 = 10

9 +f 10 = 0 となるので、加法逆元が正しいことがわかる

同じように有限体上の減算は以下のようになる

a, b ∈ Fpの場合、 a -f b = (a - b) % p

加算や減算と同じように乗算も定義できる、通常計算後に位数でモジュロ演算する

F19の場合

例）5 *f 3 = 5 +f 5 +f 5 = 15 % 19 = 15

例）8 *f 17 = 8 +f 8 +f 8...+f 8 = (8 * 17) % 19 = 3

例）7 **f3 = 7 * 7 * 7 % 19 = 343 % 19 = 1

有限体上の除算はちょっとわかりづらい

通常除算は乗算の逆算になる

F19の場合

例）3 *f 7 = 21 % 19 = 2 は 2 /f 7 = 3 を表す

しかし、 3 *f 7 = 2 を知らない状態で、どうやって 2 /f 7 を計算できるのか？

位数が素数pの有限体において、n > 0 に対して n **f (p - 1) は常に1となる

n ** (p - 1) % p = 1

フェルマーの小定理の証明は調べると色々出てくるので参照ください

a / b = a *f (1/b) = a *f b**-1

b**-1 = b**-1 *f 1 = b**-1 *f b**(p-1) = b**(p-2)

すなわち

b**-1 = b**(p-2)

例）2 / 7 = 2 *f 7**(19-2) = 2 *f 17**17 = 465...414 % 19 = 3

pow関数を使用できる

pow(7, 17) = 7**17 となり、3つ目の引数でモジュロ演算を行う

pow(7, 17, 19) = 7**17 % 19

class FieldElement:

    def __init__(self, num, prime):
        if num >= prime or num < 0:
            error = 'Num {} not in field range 0 to {}'.format(
                num, prime - 1)
            raise ValueError(error)
        self.num = num
        self.prime = prime

    def __repr__(self):
        return 'FieldElement_{}({})'.format(self.prime, self.num)

    def __eq__(self, other):
        if other is None:
            return False
        return self.num == other.num and self.prime == other.prime

    def __ne__(self, other):
        # this should be the inverse of the == operator
        return not (self == other)

    def __add__(self, other):
        if self.prime != other.prime:
            raise TypeError('Cannot add two numbers in different Fields')
        # self.num and other.num are the actual values
        # self.prime is what we need to mod against
        num = (self.num + other.num) % self.prime
        # We return an element of the same class
        return self.__class__(num, self.prime)

    def __sub__(self, other):
        if self.prime != other.prime:
            raise TypeError('Cannot subtract two numbers in different Fields')
        # self.num and other.num are the actual values
        # self.prime is what we need to mod against
        num = (self.num - other.num) % self.prime
        # We return an element of the same class
        return self.__class__(num, self.prime)

    def __mul__(self, other):
        if self.prime != other.prime:
            raise TypeError('Cannot multiply two numbers in different Fields')
        # self.num and other.num are the actual values
        # self.prime is what we need to mod against
        num = (self.num * other.num) % self.prime
        # We return an element of the same class
        return self.__class__(num, self.prime)

    def __pow__(self, exponent):
        n = exponent % (self.prime - 1)
        num = pow(self.num, n, self.prime)
        return self.__class__(num, self.prime)

    def __truediv__(self, other):
        if self.prime != other.prime:
            raise TypeError('Cannot divide two numbers in different Fields')
        # self.num and other.num are the actual values
        # self.prime is what we need to mod against
        # use fermat's little theorem:
        # self.num**(p-1) % p == 1
        # this means:
        # 1/n == pow(n, p-2, p)
        num = (self.num * pow(other.num, self.prime - 2, self.prime)) % self.prime
        # We return an element of the same class
        return self.__class__(num, self.prime)