[Bitcoin] 楕円曲線:点の加算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Point:
 
    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))
 
    def __add__(self, other):
        if self.a != other.a or self.b != other.b:
            raise TypeError('Points {}, {} are not on the same curve'.format(self, other))
 
        if self.x == other.x and self.y != other.y:
            return self.__class__(None, None, self.a, self.b)
 
        if self.x is None:
            return other
        if other.x is None:
            return self
 
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y \
            and self.a == other.a and self.b == other.b
 
    def __ne__(self, other):
        return not (self == other)
 
p1 = Point(-1, -1, 5, 7)
p2 = Point(-1, 1, 5, 7)
inf = Point(None, None, 5, 7)
print(p1 + inf)
print(inf + p2)
print(p1 + p2)

$ python3 app.py
<__main__.Point object at 0x7f014fc2fbb0>
<__main__.Point object at 0x7f014fbf07f0>
None

### x1 != x2 の点の加算
P1 = (x1,y1), P2 = (x2, y2), P3 = (x3, y3)
s = (y2 – y1)/(x2 – x1)
x3 = s^2 – x1 – x2
y3 = s(x1 – x3) – y1

1
2
3
4
5
6
x1, y1 = 2, 5
x2, y2 = -1, -1
s = (y2 - y1) / (x2 - x1)
x3 = s**2 - x1 - x2
y3 = s * (x1 - x3) - y1
print(x3, y3)
1
2
3
4
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)

### P1 = P2 の時の点の加算
x3 = s^2 – 2×1
y3 = s(x1 – x3) – y1

1
2
3
4
5
a, x1, y1 = 5, -1, -1
s = (3 * x1**2 + a) / (2 * y1)
x3 = s**2 - 2*x1
y3 = s * (x1 - x3) - y1
print(x3, y3)
1
2
3
4
5
6
7
8
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)
 
if self == other and self.y == 0 * self.x:
    return self.__class__(None, None, self.a, self.b)

なるほどー