18.783 Lecture 2 Proof of associativity.sagews

For affine points $P_1=(x_1,y_1,1)$ and $P_2=(x_2,y_2,1)$ the sum $P_1+P_2=P_3=(x_3,y_3,1)\ne 0$ is computed via:

$m = \frac{y_2-y_1}{x_2-x_1}$   (if $x_1\ne x_2$)      $m = \frac{3x_1^2+A}{2y_1}$    (if $x_1=x_2$)

$x_3 = m^2 - x_1 - x_2$;

$y_3 = m(x_3-x_1) + y_1$.

Let's verify that this operation is associative, i.e. $(P+Q)+R=P+(Q+R)$

Note that the equations are independent of the curve parameters, but we will need to use the fact that the points all satisfy the curve equation

$y^2=x^3 + Ax+B$.

RR.<Px,Py,Qx,Qy,Rx,Ry,A,B> = PolynomialRing(QQ,8)
# represent projective points on E uniquely, as either affine points (x,y,1) or the point O=(0,1,0) at infinity
P=(Px,Py,1); Q=(Qx,Qy,1); R=(Rx,Ry,1); O=(0,1,0);
I=RR.ideal(Py^2-Px^3-A*Px-B, Qy^2-Qx^3-A*Qx-B, Ry^2-Rx^3-A*Rx-B)
SS=RR.quotient(I)

def add(P,Q):
    """ general addition algorithm for an elliptic curve in short Weierstrass form"""
    if P == O: return Q
    if Q == O: return P
    assert P[2] == 1 and Q[2] == 1  # we are using affine formulas, so make sure points are in affine form
    x1=P[0]; y1=P[1]; x2=Q[0]; y2=Q[1];
    if x1 != x2:
        m = (y2-y1)/(x2-x1)         # usual case: P and Q are distinct and not opposites
    else:
        if y1 == -y2: return O      # P = -Q (includes case where P=Q is 2-torsion)
        m = (3*x1^2+A) / (2*y1)     # P = Q so we are doubling
    x3 = m^2-x1-x2
    y3 = m*(x1-x3)-y1
    return (x3,y3,1)

def negate(P):
    if P == O: return O
    return (P[0],-P[1],P[2])
    
def reduced_fractions_equal(p,q):
    return SS(p.numerator()*q.denominator()-p.denominator()*q.numerator()) == 0
    
def on_curve(P):
    return reduced_fractions_equal(P[1]^2*P[2],P[0]^3+A*P[0]*P[2]^2+B*P[2]^3)
    
def equal(P,Q):
    return reduced_fractions_equal(P[0]*Q[2],Q[0]*P[2]) and reduced_fractions_equal(P[1]*Q[2],Q[1]*P[2])

As a sanity check, let's first verify that the output of add($P$,$Q$) is always on the curve, and check the identity, inverses, and commutativity

print on_curve(O) and on_curve(negate(P)) and on_curve(add(P,Q)) and on_curve(add(P,P)) and on_curve(add(P,negate(P)))
print add(P,O) == P and add(O,P) == P
print add(P,negate(P)) == O
print add(P,Q) == add(Q,P)

Good, now for associativity in the general case...

add(add(P,Q),R) == add(P,add(Q,R))

False

Oops, we forgot to use the curve equation, we need to use our "equal" function which reduces into the quotient ring.

equal(add(add(P,Q),R),add(P,add(Q,R)))

True

Now check the cases where 2 points are equal,

equal(add(add(P,P),Q),add(P,add(P,Q))) and equal(add(add(P,Q),P),add(P,add(Q,P))) and equal(add(add(Q,P),P),add(Q,add(P,P)))

True

and also cases where 2 points are opposites,

S = negate(P);
equal(add(add(P,S),Q),add(P,add(S,Q))) and equal(add(add(P,Q),S),add(P,add(Q,S))) and equal(add(add(Q,P),S),add(Q,add(P,S)))

True

and when all 3 points are equal

equal(add(add(P,P),P),add(P,add(P,P)))

True

Just to be paranoid, also check cases where R is P+Q, P-Q, or -(P+Q),

equal(add(add(P,Q),add(P,Q)),add(P,add(Q,add(P,Q)))) and equal(add(add(P,Q),add(P,negate(Q))),add(P,add(Q,add(P,negate(Q))))) and equal(add(add(P,Q),negate(add(P,Q))),add(P,add(Q,negate(add(P,Q)))))

True

and cases where R is 2P or -2P

equal(add(add(P,Q),add(P,P)),add(P,add(Q,add(P,P)))) and equal(add(add(P,Q),negate(add(P,P))),add(P,add(Q,negate(add(P,P)))))

True

Just in case this all looked too easy, take a look at what is actually being compared...

print add(add(P,Q),R), "\n\n    versus   \n\n", add(P,add(Q,R))