[밑바닥비트코인] 2. 유한체의 연산

유한체에서의 연산은 기존 우리가 알고있는 연산과는 조금 다른 방식으로 수행된다. 

 

유한체 연산의 바탕이 되는 나머지 연산에 대해서 살펴보고 유한체 연산하는 방법을 알아보겠다. 

 

 

나머지 연산 

---

나머지 연산은 어떤 수 A를 B로 나눠서 생긴 나머지를 연산한다. 

>>> a = 10
>>> b = 4
>>> a % b
2

10 = 4*2 + 2 이므로 몫 2 나머지 2 중에 나머지인 2를 출력한다. 

 

나머지 연산은 음수에 대한 값도 가능하다. 

>>> -19 % 3
2
>>> -44 % 12
4
>>> -43 % 12
5

-19 나누기 3은 몫이 -7, 나머지가 2이다. 

 

쉽게 생각하면 나누는 수(12)를 해당 음수(-44)와 가장 가까우면서 더 작은 수(-48)로 만들었을 때의 차이를 

 

계산한다고 보면 된다. 

 

 

 

유한체의 연산

---

유한체의 연산은 나머지 연산을 바탕으로 계산한다. 

 

유한체 원소 간의 연산(ex - 덧셈)을 우리가 아는 그 연산!대로 수행하고, 이를 해당 유한체의 위수 p로 나머지 연산한다.

 

이것이 유한체 연산의 방식이다. 참 쉽죠? 

 

마찬가지로 덧셈에 대한 역원 또한 나머지 연산하여 구한다.

 

예를 들어 위수가 19인 유한체에서 9인 원소가 있다. 그렇다면 유한체 연산 -9는 -9 % 19 = 10이므로 

 

9의 덧셈에 대한 역원인 -9는 10이 되는 셈이다. 

 

파이썬으로 유한체에서의 덧셈을 구현해보자. 

 

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

FieldElement 클래스에서 __add__ 함수를 통해 + 연산자를 재정의 하였다. 

 

FieldElement 객체 간의 num을 더하고 위수로 나눈 값을 num으로 갖는 자기자신 클래스(FieldElement)를 반환한다. 

    element1 = FieldElement(9, 17)
    element2 = FieldElement(12, 17)
    print(element1+element2)

결과값 >>>
FieldElement_17(4)

각각 뺄셈과 곱셈인 __sub__ , __mul__ 함수도 거의 유사하게 구현이 가능하다. 

    def __pow__(self, power):
        num = (self.num ** power) % self.prime
        return self.__class__(num, self.prime)

거듭제곱은 지수를 인수로 받아서 연산하고 나머지 연산한 num을 갖는 객체를 반환하는 식으로 구현한다. 

 

유한체에서의 나눗셈 연산이 조금 복잡한데, 아래의 조건을 먼저 기억하도록 하자. 

출처 : https://www.quora.com/What-is-Fermats-little-theorem

 

페르마의 소정리에 따르면, 0보다 큰 수인 a에 대해서 소수인 p-1을 거듭제곱한 뒤 p로 나머지 연산하면

 

결과값은 항상 1이다. 

예를 들어 0보다 큰 수 20에 대해서 소수 인 7에서 1을 뺀 값, 즉 6을 거듭제곱하고 이를 7로 나머지 연산한 값은 1이다. 

 

이를 유한체에서의 나눗셈에 이용할 수 있다. 

1.  a / b 는 a * b^-1와 동치이다. 

2.  b^(p-1) = 1 이다. 

3. b^-1 = b^-1 * 1 = b^-1 * b^(p-1) = b^(p-2)

4. a / b = a * b^(p-2)

나눗셈 연산을 코드로 구현해보자. 

    def __truediv__(self, other):
        if self.prime != other.prime:
            raise TypeError('Cannot add two numbers in different Fields')
        num = (self.num * (other**(self.prime-2)).num) % self.prime
        return self.__class__(num, self.prime)

    element1 = FieldElement(3, 31)
    element2 = FieldElement(24, 31)
    print(element1/element2)
    
    결과값>>>
    FieldElement_31(4)

 

마지막으로 음수의 거듭제곱을 지원할 수 있도록 __pow__ 함수를 수정하도록 하겠다. 

 

페르마의 소정리에 따라서 a^p-1은 항상 1이기 때문에, k를 음수라고 가정한다면

 

a^k = a^k * a^p-1 = a^k * a^p-1 * a^p-1  . . . . . . 이 가능하다. 

    def __pow__(self, power):
        while power < 0:
            power = power + self.prime-1
        num = (self.num ** power) % self.prime
        return self.__class__(num, self.prime)

지수가 더이상 음수가 아닐때까지 a^p-1를 곱해주면 된다. 

    element1 = FieldElement(7, 13)
    element2 = FieldElement(8, 13)
    print(element1**(-3) == element2)
    
    결과값 >>>
    True

 

지금까지 유한체에서의 원소간 사칙연산을 알아보았다. 

 

다음 장부터는 이를 기반으로 이루어진 암호화 기법에 대해서 살펴보도록 하겠다.