Revision history [back]

This was started as a comment, but it ran out of space. So it became an answer.

Please fix the representation of the "zero" on the curve. The comment

# check P == O
if P == [0, 0]:
    return Q

shows where things may go wrong. Explicitly:

Please use (for the own safety) different notations for different objects (of different classes). For instance, P should not stay for both an "elliptic curve point" like P = E(20,32) and a vector like in the return [0,0] of the functions used.
How is E(0), the point at infinity, represented as a vector?

A possible way to avoid all problems is to use always "true points on the elliptic curve", since they come with the whole structural functionality. For instance:

def point_add(P, Q):
    """P, Q are points on the same elliptic curve, not vectors
    """
    # check P == O
    if P.is_zero():
        return Q

    # check Q == O
    if Q.is_zero():
        return P

    x1, y1 = P.xy()
    x2, y2 = Q.xy()

    # check Q == -P
    if x1 == x2 and y1 + y2 == 0:
        return P.curve()(0)

    # check P == Q
    if P == Q:
        return point_double(P)

    slope = F( (y2 - y1)/(x2 - x1) )
    x3 = F( slope**2 - x1 - x2 )
    y3 = F( slope * (x1 - x3) - y1 )

    return P.curve()( x3, y3 )

It is a good idea to write a function, then test it immediately. (Some IDE's ~ integrated development environments like eclipse and pycharm give a good, supported debug framework.) In this case:

Then

E = EllipticCurve( GF(37), [7, 25] )
P = E( 20, 32 )
Q = E(  1, 12 )
point_add( P, Q )

delivers

sage: E = EllipticCurve( GF(37), [7, 25] )
....: P = E( 20, 32 )
....: Q = E(  1, 12 )
....: point_add( P, Q )
....: 
(25 : 27 : 1)

One should also add in a test suite the particular cases, for instance:

sage: point_add( P, E(0) )
(20 : 32 : 1)
sage: point_add( P, E(0) ) == P
True
sage: point_add( E(0), P )
(20 : 32 : 1)
sage: point_add( E(0), P ) == P
True
sage: point_add( P, -P )
(0 : 1 : 0)
sage: point_add( P, -P ).is_zero()
True

To the posted question, the simple answer would have been: "(0,0) is not a point on the curve, but some functions return it..."