Hi there,
I’m reading the book ‘Programming bitcoin : Learn How to Program Bitcoin from Scratch’ by Jimmy Song. I’ve just finished chapters 1 and 2 about finite fields and elliptic curves. I understand all the math and all the exercises. Since all the answers are in the book, reproducing the code so far was easy.
I’m now combining chapter 2 (that produced a class ‘FieldElement’ ) and 3 (that produced a class ‘Point’)
Goal is to define two points P1 and P2 and then do point addition on a preset Field with order prime.
The code I have works fine… exept for the case that P1 = P2 and the y-coordinate is not zero.
(I’m checking my answers with the table of point additions on Elliptic Curves over Finite Fields and it works fine)
Here’s the error:
Here’s my code:
class FieldElement:
def __init__(self, num, prime):
if num >= prime or num < 0:
error = 'num {} is not part of field 0 to {}'.format(num, prime - 1)
raise ValueError(error)
self.num = num
self.prime = prime
def __repr__(self):
return 'FieldElement_{}({})'.format(self.prime, self.num)
def __eq__(self, other):
if other is None:
return False
return self.num == other.num and self.prime == other.prime
def __ne__(self, other):
return not (self == other)
def __add__(self, other):
if self.prime != other.prime:
raise TypeError('You cannot add two numbers in different fields!')
num = (self.num + other.num) % self.prime
# return self.__class__(num, self.prime)
return self.__class__(num, self.prime)
def __sub__(self, other):
if self.prime != other.prime:
raise TypeError('You cannot subtract two numbers in different fields!')
num = (self.num - other.num) % self.prime
return self.__class__(num, self.prime)
def __mul__(self, other):
if self.prime != other.prime:
raise TypeError('You cannot multiply two numbers in different fields!')
num = (self.num * other.num) % self.prime
return self.__class__(num, self.prime)
def __pow__(self, exponent):
if exponent < 0:
exponent = prime - 1 + exponent
num = (pow(self.num, exponent, self.prime))
return self.__class__(num, self.prime)
def __truediv__(self, other):
if self.prime != other.prime:
raise TypeError('You cannot divide two numbers in different fields!')
num = self.num * pow(other.num, self.prime - 2, self.prime) % self.prime
return self.__class__(num, self.prime)
class Point:
def __init__(self, x, y, a, b):
self.a = a
self.b = b
self.x = x
self.y = y
#Check if you're dealing with the point of infinity:
if self.x is None and self.y is None:
return
#If not, than act as normal:
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 other.a != other.a or other.b != other.b:
raise TypeError('Points {}, {} are not on the same curves!'.format(self, other))
#Check for point of infinity:
if self.x is None:
return other
if other.x is None:
return self
# Check on inverse additieve property
# That means the x of P1 en P2 is equal, but y differs so that means a vertical line
# If so, return the point of infinity:
if self.x == other.x and self.y != other.y:
return self.__class__(None, None, self.a, self.b)
# P1 does not equal P2
if self.x != other.x:
h = (other.y - self.y) / (other.x - self.x)
x = h ** 2 - self.x - other.x
y = h * (self.x - x) - self.y # so NOT self.x - other.x here, because we're dealing with x3 here
return self.__class__(x, y, self.a, self.b)
# P1 = P2 and y-coordinate is not zero
if self == other and self.y != 0:
h = (3 * self.x ** 2 + self.a) / (2 * self.y)
x = h ** 2 - 2 * self.x
y = h * (self.x - x) - self.y
return self.__class__(x, y, self.a, self.b)
#P1 = P2 and y-coordinate is zero. Return the point of infinity
if self == other and self.y == 0:
return self.__class__(None, None, self.a, self.b)
def __repr__(self):
return "The point addition gives: {}, {}".format(self.x, self.y)
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)
prime = 103
a = FieldElement(0, prime)
b = FieldElement(7, prime)
x1 = FieldElement(1, prime)
y1 = FieldElement(76, prime)
x2 = FieldElement(1, prime)
y2 = FieldElement(76, prime)
p1 = Point(x1, y1, a, b)
p2 = Point(x2, y2, a, b)
print(p1+p2)
The only thing I did different than in the book is adding
and self.y != 0
to the first line of the situation that P1 = P1 and y-coordinate is not zero (in the add()-method of the Point class) because the denominator cannot be zero.
The errortype is relatively simple, but I just don’t see what I did wrong.
I’m overlooking something, but what?
Any help is appreciated, thanks in advance.
