타원곡선 덧셈

타원곡선 위의 점 덧셈 기본원리는 아래 그림과 같다.

 

출처: 밑바닥부터 시작하는 비트코인

 

덧셈에 대한 모든 케이스는 아래 세가지로 나눠서 따져봐야한다.

 

1. 두 점이 x 축에 수직인 직선 위에 있는 경우

출처: 밑바닥부터 시작하는 비트코인

 

p1 = Point(-1, -1, 5, 7)
p2 = Point(-1, 1, 5, 7)
inf = Point(None, None, 5, 7)
print(p1 + inf == p1)
print(p2 + inf == p2)
print(p1 + p2 == inf)

 

def __add__(self, other):
	# None 은 무한원점을 의미한다. self 가 무한원점이면, other 를 리턴. ex) A(other) + I(self) = A
	if self.x is None:
		return other

	# other.x 가 무한원점이면, self 를 리턴함. ex) A(self) + I(other) = A
		if other.x is None:
			return self
		
	# 연습문제 2.3
	# 한 점에 그의 역원을 더하는 경우를 코딩해라.
	# 두 점은 x 가 같고 y 는 다른 경우이며 두 점을 이은 직선은 x축에 수직이다. 반환된 결과는 무한원점이어야 한다.
	if self.x == other.x and self.y != other.y:
		return self.__class__(None, None, self.a, self.b)

 

2. 두 점이 x 축에 수직인 직선 위에 있지 않은 경우

$P_1 = (x_1, y_1) $, $P_2 = (x_2, y_2) $, $P_3 = (x_3, y_3) $
$P_1 + P_2$ 더해서 $P_3$ 을 알고 싶다.

 

공식이  필요. 먼저 기울기를 구한다.
s = $(y_2 - y_1)/(x_2 - x_1)$
$x_3 = s^2 - x_1 - x_2$
$y_3 = s(x_1 - x_3) - y_1$

 

# 연습문제 2.5
if self.x != other.x:
	s = (other.y - self.y) / (other.x - self.x)
	x = s ** 2 - self.x - other.x
	y = s * (self.x - x) - self.y
	return self.__class__(x, y, self.a, self.b)

 

3. 두 점이 같은 경우 

출처: 밑바닥부터 시작하는 비트코인

$P_1 = (x_1, y_1) $, $P_1 = (x_1, y_1) $, $P_3 = (x_3, y_3) $
$P_1 + P_1$ 더해서 $P_3$ 을 알고 싶다.

 

기울기를 구해야되는데 미분이 필요하다.
$y^2 = x^3 + ax + b$ 양변을 미분한다.
$dy/dx = 3x^2 + a / 2y$

 

$s = (3x_1^2 + a) / (2y_1)$
$x_3 = s^2 - 2x_1$
$y_3 = s(x_1 - x_3) - y_1$

 

# 연습문제 2.7
if self == other:
	s = (3 * self.x ** 2 + self.a) / (2 * self.y)
	x = s ** 2 - 2 * self.x
	y = s * (self.x - x) - self.y
	return self.__class__(x, y, self.a, self.b)

 

4. 예외 처리

출처: 밑바닥부터 시작하는 비트코인

 

P1 = P2 이면서 y 가 0인 케이스다. 무한원점 리턴한다.

 

# 덧셈 예외처리. 접선이 x 축에 수직인 경우 p81. P1 = P2 이면서 y 좌표가 0인 경우
if self == other and self.y == 0 * self.x:
	return self.__class__(None, None, self.a, self.b)

 

출처: 밑바닥부터 시작하는 비트코인