이번 세미나에서는 1장. 유한체를 다룹니다.

이번 장은 현대 대수학 좀 더 정확히는 추상 대수를 다룹니다. 추상 대수는 상당한 노력과 시간을 요구하는 것이지만, 지미 송은 적당한 수준으로 쉽게 익힐 수 있도록 안내하고 있습니다.

원서로 스터디를 진행할 때는 내용도 내용(수학을 다룬다는 것)이지만 원어로 읽어야 하는 부담도 컸습니다. 번역서로 다시 스터디를 진행하니 내용에만 집중할 수 있어서 좋습니다. 번역서 또한 고품질의 번역이라 시간만 내고 책 내용을 꼼꼼하게 따라간다면 어렵지 않게 정복할 수 있을 것입니다. 최고의 품질로 번역해 준 역자에게 다시 한 번 감사드립니다.

본문 내용을 전체적으로 한 번 읽습니다. 본문 내용을 읽을 때 명심할 점은 직접 코딩을 해야 한다는 것입니다.

아래 인용한 본문 내용을 다시 한 번 읽어 봅니다. 본문 그대로가 아니라 제가 일부 편집했거나 제 의견이 들어간 부분은 높임말로 표현했습니다.

타원곡선 암호는 저자 서명과 이의 검증에 사용되는데 이는 트랜잭션 작동 방법의 핵심 알고리즘이다.
- 비트코인 프로그래밍에 있어 유한체와 타원곡선을 먼저 알게 되면 필요한 선수 개념을 확실히 이해하게 되어 체계적인 학습이 가능하다.
유한체에서는 나눗셈을 정의하는 것이 가장 까다롭다.
- 페르마의 작은 정리(소정리)를 활용해야 합니다.
  - 1 = n^(p-1) % p
- 예) a / b = a · b^-1
  - b^-1 = b^-1· 1 = b^-1· b^(p-1) = b^(p-2)
  - b^-1 = b^(p-2)
- 예) p가 19인 경우, 2 / 7
  - 2 · 7¹⁷ % 19 = 3
유한체의 원소의 갯수를 위수라고 한다.
나머지연산으로 덧셈, 뺄셈, 곱셈, 나눗셈에 대해 닫혀 있는 유한체를 만들 수 있다.
원소의 갯수가 p개인 집합을 가장 직관적으로 표기 한다면, {0, 1, 2, …, p-1}와 같이 할 수 있을 것입니다.
- 숫자를 사용하지 않고도 할 수 있지만 0을 포함해서 p-1까지로 표현하는 것이 가장 직관적입니다. 서로 다른 원소가 p개 있음을 직관적으로 알 수 있습니다.
- 유한체는 나머지연산으로 만들 수 있으니 p로 나눈 나머지가 원소가 되어야 하니, 여기에도 잘 부합합니다.
유한체의 위수는 항상 소수이거나 소수의 거듭제곱이다.
- 유한체는 임의의 원소 k로 전체 집합에 곱했을 때 그 결과가 다시 원래 집합이어야 한다.
- 연습문제 1.5의 NOTE_의 주석을 보면 알 수 있듯이 p값이 소수가 아닌 경우 원래 집합이 아닌 결과를 얻을 수 있습니다.

본문에서는 다루고 있지 않지만 좀 더 깊은 이야기를 해 보겠습니다.

체는 추상대수의 주제이고, 추상대수는 수학적 구조를 다룹니다. 하나의 연산 만을 다루는 구조에서는 그 연산을 덧셈이라 하고, 두 개의 연산을 다루는 구조에서는 하나는 덧셈으로 다른 하나는 곱셈이라 합니다. 추상대수에서 덧셈이라는 이름과 곱셈이라는 이름을 사용하는 이유는 이미 우리가 초등수학을 통해 이 이름들에 익숙해 있기 때문입니다. 그리고 실제로 우리가 다루는 실수가 체에 해당하는 것으로, 체에 대한 정의 없이 ‘덧셈은 이렇게 하는거야, 곱셈은 이렇게 하는거야’라는 정의만 가지고 연산을 해 왔던 것입니다.

체는 유한체 정의에서 알 수 있듯이 두 가지 연산을 다루는 구조입니다. 두 가지 연산을 다룰 때 어떤 것을 덧셈이라고 할지 어떤 것을 곱셈이라고 할지는 분배법칙을 만족하는 성질에 따라 결정됩니다. 분배법칙은 다음과 같습니다. a # (b @ c) = (a # b) @ (a # c). 여기에서 #에 위치하는 연산이 곱셈이고, @에 위치할 연산이 덧셈입니다.

Modulo Arithmetic(나머지 연산)에서 우리가 아는 덧셈과 곱셈이 아닌, 이름은 같지만 연산 방법이 다른 덧셈과 곱셈을 다룹니다.

코딩 부분에 대해서도 좀 더 이야기 해 봅시다.

먼저 개념적으로 유한체가 있고 유한체 원소가 있습니다.
- 본문에서는 유한체 원소만을 구현하고 있지만 좀 더 정확히는 유한체 또한 구현해야 합니다.
  - FiniteField, FiniteFieldElement
유한체의 연산은 실제적으로는 유한체 요소들 사이의 연산임으로 유한체 원소에 정의되는게 적당합니다.
유한체는 p값이 무엇이냐에 따라 달라지므로 유한체를 생성할 때는 위수(order)가 설정되어야 합니다.
- 위수는 order가 적당해 보이지만 보통 p를 사용함으로 p라고 해도 됩니다.
  - FiniteField
    - __init__(self, p)
      - self.p = p
본문에 나와 있는 연습문제들을 풀기 위해서는 정수를 다룰 수 있어야 합니다.
- 정수 값을 입력으로 유한체 원소로 출력할 수 있도록 합니다.
  - FiniteField
    - toFiniteFieldElement(self, n)
      - return FiniteFieldElement(n, self.p)

class FiniteFieldElement: 

    def __init__(self, n, p): 
        self.n = n
        self.p = p
        
    def __repr__(self):
        return 'FiniteFieldElement_{}({})'.format(self.p, self.n)


class FiniteField: 

    def __init__(self, p): 
        self.p = p

    def toFiniteFieldElement(self, n):
        return FiniteFieldElement(n, self.p)


f_19 = FiniteField(19)
a = f_19.toFiniteFieldElement(7)
print(a)

class FiniteFieldElement:

def __init__(self, n, p):

self.n = n

self.p = p

def __repr__(self):

return 'FiniteFieldElement_{}({})'.format(self.p, self.n)

class FiniteField:

def __init__(self, p):

self.p = p

def toFiniteFieldElement(self, n):

return FiniteFieldElement(n, self.p)

f_19 = FiniteField(19)

a = f_19.toFiniteFieldElement(7)

print(a)

참고 자료

[1] ‘닫혀있다’, ‘항등원’, ‘역원’에 대해서 분명한 개념이 떠오르지 않는다면 칸 아카데미 수학을 먼저 학습하시길 추천합니다. 기억을 되살리기 위한 목적이니 최대한 빠르게 1주일 내로 학습을 마치길 권합니다. 전체를 볼 시간이 없으면 연산 법칙 부분 만이라도 빠르게 학습하십시오.

[2] 암호학에 관련된 칸 아카데미 강좌도 도움이 됩니다.

[3] 체에 대한 좀 더 정확한 정의는 아래 링크를 참조하세요. 저자는 어떤 이유인지 교환법칙, 결합법칙, 분배법칙이 성립해야 함에 대해서는 제외하고 있습니다. http://www.ktword.co.kr/word/abbr_view.php?m_temp1=3860