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
사칙 연산을 집합 안에서 소화할 수 있는 집합
그런데,
즉,
pow(7, 17)
: 일반 속도 (7**17)pow(7, 17, 19)
: 빠른 속도 (7**17%19)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가 소수이면, 모든 정수 에 대해 이다.
혹은 가 소수이고 가 의 배수가 아니면, 이다.
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]
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)