Finite Field

최완식·2023년 1월 9일
1

Bitcoin Programming

목록 보기
1/8
post-thumbnail

Bitcoin Programming 책을 읽으며 이해한 내용에 대해 정리한다. 첫번째는 유한체이다.

환경 설치

// 파이썬 3.5 이상 버전 설치

// pip 설치
curl https://bootstrap.pypa.io/get-pip.py -o get-pip.py

// 스크립트 실행
python3 get-pip.py

// Git 설치
// https://git-scm.com/downloads

// 책 소스코드 받기
git clone https://github.com/jimmysong/programmingbitcoin
cd programmingbitcoin

// virtualenv 설치
pip install virtualenv --user

// 가상 환경 만들기
python3 -m virtualenv venv

// 가상 환경 venv 생성 후, 내부 activate 실행 (가상 환경 만들면 해당 폴더에 이름 적은 폴더가 생긴다.)
source venv/bin/activate

// 요구 라이브러리 설치
pip install -r requirements.txt

// jupyter notebook 실행
jupyter notebook

체 (Field)

사칙 연산을 집합 안에서 소화할 수 있는 집합

  • 즉, 연산을 통해 나온 값 또한 해당 집합의 원소여야 한다.
  • 유리수, 실수, 복소수의 경우 체의 조건을 만족한다.
  • 정수는 안된다. (나눗셈 -> 유리수)
  • 여기서 엄밀한 증명을 하자는 것은 아니니 직관적으로 이해하고 넘어가자.

유한체 (Finite field)

  • 유리수체, 실수체, 복소수체의 특징은 무한 집합이다.
  • 그렇다면 유한집합인 체도 있는가?
  • 그 방법중 하나가 유한체이다.
  • 유한체에서는 정수체(Z)에서 소수로 나눈 나머지를 관찰하는 것을 통해 유한집합체를 만들어낸다.
  • 예컨데, 7과 같은 소수로 나눈 나머지가 같은 원소들은 모두 같은 것으로 취급하는 것이다.
    • 158(mod7)15≡8 (mod 7)
  • 즉, 소수로 나눈 나머지들을 원소로 하는 집합 Zp\mathbb Z_p를 정의 하자.
    • Z7=0,1,2,3,4,5,6\mathbb Z_7 = {0,1,2,3,4,5,6}
  • 여기서 p를 위수(order)라 한다.

체의 증명

  • 체 인지 확인하기 위해서는 간단히 생각했을 때 사칙 연산에 대해 닫혀있는지 확인하면 된다.
  • 덧셈, 곱셈, 뺄셈에 대해서는 자명하다.
  • 나눗셈이 문제다.

나눗셈

  • 유한체 원소들 간의 나눗셈 결과는 어떻게 될까? 쉽게 예상하기 어렵다.
  • 그렇기 때문에 곱셈으로 부터 나눗셈의 결과를 예측해보는 것이 도움이 된다.
  • F19F_{19}에 속한 원소(0~18)에 대해 확인해보자.
  • 37=213 \cdot 7 = 21 % 19 = 2, 즉 2/7=32 / 7 = 3
  • 그럼 나눗셈을 할 때마다 이렇게 계산해야 할까?
  • 여기서 페르마의 소정리를 사용할 수 있다.
  • n(p1)%p=1n^{(p-1)} \% p = 1

증명

  • 여기서 사칙 연산은 모듈러 연산을 말함
a/b=ab1a/b = a \cdot b^{-1}

그런데,

bp1=1b1=b11=b1bp1=bp2b^{p-1} = 1 b^{-1} = b^{-1} \cdot 1 = b^{-1} \cdot b^{p-1} = b^{p-2}

즉,

b1=bp2b^{-1} = b^{p-2}
  • 이렇게 되면 나누기를 거듭제곱으로 변경해서 구할 수 있다는 말이된다.
2/7=27(192)=2717=465261027974414%19=32/7 = 2 \cdot 7^{(19-2)} = 2 \cdot 7^{17} = 465261027974414 \% 19 = 3
  • 여기서 지수가 커지게 되면 계산시간은 더 길어질 가능성이 높다.
  • python에서 pow 연산은 내부적으로 더 빠른 연산을 지원한다.
    • pow(7, 17): 일반 속도 (7**17)
    • pow(7, 17, 19): 빠른 속도 (7**17%19)
      • 모듈러 연산 특징을 사용하여 각 곱셈마다 값의 크기를 줄여서 계산
      • 모듈러는 음수에 적용했을 시 보수의 모듈러가 적용되어 양수로 떨어진다.

위수가 소수인 유한체가 유용한 이유

F19={k0,k1,k2,...k18}(k>0,kZ)F_{19} = \{ k \cdot 0, k \cdot 1, k \cdot 2, ... k \cdot 18 \} (k > 0, k \in \mathbb{Z})
  • 위수가 소수인 유한체의 경우, 유한체에 0이 아닌 원소 k로 전체 집합을 곱하면 그 결과는 다시 원래 집합이 된다.
    • 원소의 배열 순서는 달라지나, 집합이기 때문에 순서는 상관 없다.
  • 만약 위수가 합성수라면, 곱하는 수에 따라 집합이 달라지게 된다.
    • 더 나누어 떨어져 중복되는 원소가 발생할 수 있기 때문
    • 개수가 더 작아진다.
  • 소수의 특징때문에 나타나는 성질이다.
prime = 19
candidates = [1, 3, 7, 13, 18, 2985]
for cand in candidates:
    result = []
    for i in range(0, 19):
        result.append((i*k)%prime)
    result.sort()
    print(result)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]

페르마의 소정리

p가 소수이면, 모든 정수 aa에 대해 apa(mod p)a^p\equiv a\left({\rm mod}\ p\right)이다.

혹은 pp가 소수이고 aapp의 배수가 아니면, ap11(mod p)a^{p-1}\equiv 1\left({\rm mod}\ p\right) 이다.

prime = 43
result = []
for p in range(0, prime):
    element = FieldElement(p, prime)**(prime-1)
    result.append(element.num)
result.sort()
print(result)
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

FieldElement Class

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): # !=
        return not (self == other)

    def __add__(self, other): # +
        if self.prime != other.prime: 
            raise TypeError('Cannot add two numbers in different Fields')
        result = (self.num + other.num) % self.prime  
        return self.__class__(result, self.prime)  

    def __sub__(self, other): # -
        if self.prime != other.prime:
            raise TypeError('Cannot subtract two numbers in different Fields')
        result = (self.num - other.num) % self.prime
        return self.__class__(result, self.prime)

    def __mul__(self, other): # *
        if self.prime != other.prime:
            raise TypeError('Cannot multiply two numbers in different Fields')
        result = (self.num * other.num) % self.prime
        return self.__class__(result, self.prime)

    def __pow__(self, exponent): # **
        n = exponent % (self.prime - 1)
        result = pow(self.num, n, self.prime) # 파이썬에서 제공하는 빠른 거듭제곱 모듈러 연산
        return self.__class__(result, self.prime)

    def __truediv__(self, other): # 실수 나눗셈 연산 (/) - 정수의 경우 __floordiv__(//)를 통해 할 수 있다.
        if self.prime != other.prime:
            raise TypeError('Cannot divide two numbers in different Fields')
        other_num = other.num**self.prime-2
        result = (self.num * other_num) % self.prime
        return self.__class__(result, self.prime)

Reference

profile
Goal, Plan, Execute.

0개의 댓글