유한체에서 정의된 타원곡선 위의 두점 덧셈

[yangbongsoo]

유한체에서 정의된 타원곡선

유한체에서 정의되었기 때문에 타원곡선 모양이 실수체에서 정의된것과 많이 다르다. 유한체 원소들은 연속적이지 않기 때문이다. 유일하게 관찰되는 패턴은, $y^2$ 항 때문에 y 축의 중간값(100) 을 지나는 수평축을 기준으로 대칭이다. 실수체에서의 곡선처럼 x 축으로 대칭도 아니다. 유한체에서 음수가 없기 때문이다.

# 연습문제 3.1
prime = 223
a = FieldElement(0, prime)
b = FieldElement(7, prime)

def on_curve(x, y):
    return y ** 2 == x ** 3 + a * x + b

print(on_curve(FieldElement(192, prime), FieldElement(105, prime)))
print(on_curve(FieldElement(17, prime), FieldElement(56, prime)))
print(on_curve(FieldElement(200, prime), FieldElement(119, prime)))
print(on_curve(FieldElement(1, prime), FieldElement(193, prime)))
print(on_curve(FieldElement(42, prime), FieldElement(99, prime)))

prime = 223
a = FieldElement(0, prime)
b = FieldElement(7, prime)
x = FieldElement(192, prime)
y = FieldElement(105, prime)
p1 = Point(x, y, a, b)

init 에서 해당 Point 가 타원곡선 위에 있는지 검사하는 연산은 FieldElement 에서 재정의한 operation 을 사용한다.

    def __init__(self, x, y, a, b):
        self.a = a
        self.b = b
        self.x = x
        self.y = y
        if self.x is None and self.y is None:
            return

        if self.y ** 2 != self.x ** 3 + a * x + b:
            raise ValueError('({}, {}) is not on the curve'.format(x, y))

[yangbongsoo]

모든 타원곡선 방정식은 유한체에서도 유효하다.

prime = 223
a = FieldElement(0, prime)
b = FieldElement(7, prime)

x1 = FieldElement(192, prime)
y1 = FieldElement(105, prime)

x2 = FieldElement(17, prime)
y2 = FieldElement(56, prime)

p1 = Point(x1, y1, a, b)
p2 = Point(x2, y2, a, b)

p3 = Point(FieldElement(170, prime), FieldElement(142, prime), a, b)
print(p1 + p2 == p3)  # True