橢圓曲線

橢圓曲線是方程式為 $y^{2}=x^{3}+ax+b$ 的曲線

比特幣用的是 secp256k1: $y^{2}=x^{3}+7$

我們定義橢圓曲線的無窮遠點 (參考維基百科) 為

$\left( { x }_{ 1 },{ y }_{ 1 } \right) =\left( { x }_{ 1 },{ y }_{ 1 } \right) +\left( \infty ,\infty \right)$

$\left( { x }_{ 1 },{ y }_{ 1 } \right) +\left( { x }_{ 1 },{ -y }_{ 1 } \right) =\left( \infty ,\infty \right)$

(想成 0)

又定義 P + Q + R = 0，這裡的「加法」跟普通加法不一樣，是定義在曲線上的加法

算法為當

$P = (x_{p}, y_{p}), Q = (x_{Q}, y_{Q}), x_{p}\neq x_{Q}$ 時

先計算出斜率 $s = (y_{Q} - y_{p})/(x_{Q} - x_{p})$

就可以算出 $R = (x_{R} = {s}^{2} - x_{p} - x_{Q}, y_{R} = s(x_{p} - x_{R})- y_{p})$

而當 $x_{p} = x_{Q}$ 時

斜率要用微分求得

$s = (3{x_{p}}^{2} + a)/2y_{p}$，$R = (x_{R} = {s}^{2} - 2x_{p}, y_{R} = s(x_{p} - x_{R})- y_{p})$

定義 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))

$(x, y)$ 必須要在曲線上，如果 $(x, 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)