橢圓曲線
橢圓曲線是方程式為 的曲線
比特幣用的是 secp256k1:
我們定義橢圓曲線的無窮遠點 (參考維基百科) 為
(想成 0)
又定義 P + Q + R = 0,這裡的「加法」跟普通加法不一樣,是定義在曲線上的加法
算法為當
時
先計算出斜率
就可以算出
而當 時
斜率要用微分求得
,
定義 Point
class Point:
def __init__(self, x, y ,a, b):
self.x = x
self.y = y
self.a = a
self.b = b
if self.x is None and self.y is None:
return
if self.y**2 != self.x**3 + a*x + b:
raise RuntimeError('({}, {}) is not on the curve!'.format(self.x, self.y))
必須要在曲線上,如果 都是 None
,那就是橢圓曲線上的無限遠點
曲線上的加法:
def __add__(self, other):
if self.a != other.a or self.b != other.b:
raise RuntimeError('Points {}, {} are not on the same curve'.format(self, other))
if self.x is None:
return other
if other.x is None:
return self
# case1: (2, 1) + (2, -1)
if self.x == other.x and self.y != other.y:
return self.__class__(None, None, self.a, self.b)
# case2: (2, 1) + (3, 2)
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)
# case3: (2, 1) + (2, 1)
else:
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)