CoCalc Public Files18.783 Lecture 2 Proof of associativity.ipynb
Author: Andrew Sutherland
Views : 125
Description: 18.783 Lecture 2: Algebraic proof of the associativity of the elliptic curve group law on curves defined by a short Weierstrass equation.
Compute Environment: Ubuntu 20.04 (Default)

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$.

In [48]:
RR.<Px,Py,Qx,Qy,Rx,Ry,A,B> = PolynomialRing(ZZ,8) # We represent projective points on E uniquely, as 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): """ Verifies the inputs p and q are well-defined elements of the fraction field of SS in any char != 2, then tests whether they are equal as elements of the fraction field of SS. We exclude characteristic 2 because we are using formulas for curves in short Weierstrass form, but if we generalized the formulas to curves in general Weierstrass form we could also handle char 2. This is also necessary to handle all curves in char 3 (the formulas here are valid in char 3 but not every elliptic curve can be put in the form y^2 = x^3 + Ax + B in characteristic 3). Note that while we are working with polynomials over ZZ we have a will defined reduction map to polynomials over any ring. We can verify that a polynomial will be nonzero in any field of characteristic p != 2 by verifying that the GCD of the coefficients is 1 or a power of 2. """ # The call to prime_divisors below will fail on 0, which is good assert gcd(SS(p.denominator()).lift().coefficients()).prime_divisors() in [[],[2]] assert gcd(SS(q.denominator()).lift().coefficients()).prime_divisors() in [[],[2]] 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]) def passert(predicate): if eval(predicate): print("Confirmed assertion %s" % predicate) else: print("Failed to confirm assertion %s" % predicate) # raise ValueError("Assertion %s FAILED" % predicate)

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

In [49]:
Confirmed assertion 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))) Confirmed assertion add(P,O) == P and add(O,P) == P Confirmed assertion add(P,negate(P)) == O Confirmed assertion add(P,Q) == add(Q,P)

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

In [50]:

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

In [51]:

Now check the cases where 2 points are equal,

In [52]:

and also cases where 2 points are opposites,

In [53]:

and when all 3 points are equal

In [54]:

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

In [55]:

and cases where $R$ is $2P$ or $-2P$

In [56]: