타원곡선 덧셈

[yangbongsoo]

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

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

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)