elliptic_curve_basics
system:sage


<h1>SAGE Basics</h1>

{{{id=1|
1+1
///
}}}

You can enter multiple computations in one box; SAGE will evaluate them all but only print the output of the last one.

{{{id=2|
2/2
3*3
4^4
///
}}}

Note that ^ gives exponentiation.<Br>

To get multiple outputs from one line, use semicolons.

{{{id=3|
5//2; 5%2; 5/2
///
}}}

{{{id=4|
1/log(2)
///
}}}

SAGE carries out exact computations whenever possible.  To get numerical approximations, compute with real numbers.

{{{id=5|
1/log(2.0)
///
}}}

Use show() to print things nicely:

{{{id=26|
show(sqrt(2)/log(4))
///
}}}

<h2>Lists</h2>

{{{id=6|
L = [4,5/2,sqrt(-1),log(2),'spam']
L
///
}}}

Lists can contain data of multiple types.

{{{id=7|
L[1]
///
}}}

Lists are indexed with first element 0.

<p>To see what you can do to an object, use Tab
<br>To find out what a command does, use ?
<br>To get the source code, use ??

{{{id=8|
L.
///
}}}

The range(lower,upper) command is often useful.  Note that the values return are up to but <b>not including</b> the upper bound.  This will be a recurring theme.

{{{id=9|
R = range(1,10)
S = range(10)
R;S
///
}}}

Python "slice" notation lets you pick elements out of lists.

{{{id=10|
S[1:3]
///
}}}

{{{id=11|
S[:5]; S[5:]; S[::-1]
///
}}}

What will the following do?

{{{id=12|
S[5:1:-2]
///
}}}

<h1>Elliptic curves</h1>

{{{id=14|
E = EllipticCurve([-25,0])
E
///
}}}

Note that the field of definition is part of the data.

{{{id=70|
plot(E)
///
}}}

{{{id=71|
E_plot = plot(E, thickness=2, color='red', xmin=-6, xmax=10)
E_plot
///
}}}

To create a point on the curve:

{{{id=17|
P = E([0,0])
P
///
}}}

Not every point is on the curve!

{{{id=29|
Q = E([10,10])
///
}}}

Square brackets or parentheses work:

{{{id=30|
Q = E((-4,-6))
Q
///
}}}

You can enter points in projective coordinates:

{{{id=43|
Q == E((8,12,-2))
///
}}}

This is necessary to input the point at infinity.

{{{id=39|
O = E((0,1,0))
///
}}}

{{{id=19|
O.is_zero()
///
}}}

<h1>The group law</h1>

{{{id=72|
P_plot = plot(P, pointsize=50, rgbcolor=(0,0,0.5))
Q_plot = plot(Q, pointsize=50, rgbcolor=(0,0,0.5))
P_plot + Q_plot + E_plot
///
}}}

{{{id=18|
P+P
///
(0 : 1 : 0)
}}}

Multiplying P by an integer k means add P to itself k times:

{{{id=28|
2*P
///
}}}

{{{id=31|
P+Q
///
}}}

{{{id=32|
show(2*Q)
///
}}}

Rational points can get big really fast!

{{{id=33|
for i in range(10): 
    show(i*Q)
///
}}}

<h2><strong>Computer Verification of Associativity of the Group Law</strong></h2> (by William Stein)

Since we're computing with abstract variables, we define a polynomial ring that contains all of our variables.

{{{id=22|
R.<x1,y1,x2,y2,x3,y3,A,B> = PolynomialRing(QQ);   R
///
}}}

Group law algorithm (Washington p.14):

{{{id=57|
def elladd(P1, P2):
    '''Add two distinct, nonzero points on an elliptic curve.'''
    
    x1,y1 = P1[0],P1[1]
    x2,y2 = P2[0],P2[1]
    m = (y2 - y1)/(x2 - x1)  # slope
    x3 = m^2 - x1 - x2
    y3 = m*(x1-x3) - y1
    return (x3, y3)
///
}}}

<p>We define three <strong><em>generic points</em></strong>, then add them using both ways of associating.</p>

{{{id=23|
P1 = (x1,y1); P2 = (x2,y2); P3 = (x3,y3)
Z = elladd(P1, elladd(P2,P3))
W = elladd(elladd(P1,P2), P3)
Z == W
///
}}}

<p>Unfortunately, these points have coordinates that are just polynomials, so, e.g., the relationship $y_1^2 = x_1^3 + Ax_1 + B$ simply isn't taken into account.&nbsp; Thus $Z\neq W$.&nbsp; To take into the extra relationship between the $x_i$ and $y_i$, we create a quotient ring.&nbsp; This is just like how the integers modulo $n$ is a quotient ring, which takes into account the relation "$n = 0$".</p>

<h2><strong>A Polynomial Quotient Ring:</strong></h2>
<p>We thus form the quotient polynomial ring with variables $x_i, y_i, A, B$,  where $y_i^2 = x_i^3 +Ax_i + B$.&nbsp; You can think of this as a ring that  contains three <em><strong>generic points</strong></em> on the elliptic curve.</p>

{{{id=21|
rels = [y1^2 - (x1^3 + A*x1 + B), y2^2 - (x2^3 + A*x2 + B), y3^2 - (x3^3 + A*x3 + B)]
///
}}}

{{{id=60|
Q = R.quotient(rels)
Q; show(Q)
///
}}}

<p>We then verify that the two points $(P_1 + P_2)+P_3$ and $P_1 + (P_2 + P_3)$ are equal, modulo the relations, hence proving the associative law in the case where $P_1$, $P_2$, $P_3$, $P_1 + P_2$, and $P_2+P_3$ are all distinct, nonzero, and no pair are inverses of each other.</p>
<p>The <em><strong>massive</strong></em> polynomial $f$ below is $0$ in the quotient ring precisely if the $x$-coordinates of the two points are equal, modulo the relations.</p>

{{{id=37|
f = Z[0].numerator()*W[0].denominator() - Z[0].denominator()*W[0].numerator(); f
///
}}}

<p>Coerce into the quotient ring $Q$ defined above:</p>

{{{id=38|
Q(f)
///
}}}

<p>Likewise for the $y$-cordinates:</p>

{{{id=64|
Q(Z[1].numerator()*W[1].denominator() - Z[1].denominator()*W[1].numerator())
///
}}}

<h1>About the discriminant</h1>

The quantity $4A^3 + 27B^2$ is the <b>discriminant</b> of the elliptic curve $E: y^2 = x^3 + Ax + B$.  Why do we require it to be nonzero?  Let's see what happens when it is zero.

<p>$y^2 = x^3$</p>

{{{id=67|
implicit_plot(y^2-x^3,(-2,5),(-5,5))
///
}}}

$y^2 = x^3 - 3x + 2$

{{{id=69|
implicit_plot(y^2-x^3+3*x-2,(-3,5),(-5,5))
///
}}}

<p>Both of these curves have <b>singularites</b> -- points where the tangent line is undefined.  If we try to define the group law on these curves using our formulas, we run into a problem when trying to double or add singular points.  Thus we exclude these types of curves in our definition of elliptic curve.</p>

<p>We can define the group law on the <b>nonsingular</b> real-valued points of these curves.  In the first example, the curve has a <b>cusp</b>, and the resulting group $E_{ns}(\mathbf{R})$ is isomorphic to the additive group of real numbers.  In the second example, the curve has a <b>node</b>, and the resulting group $E_{ns}(\mathbf{R})$ is isomorphic to the multiplicative group of real numbers.  Over general fields the second case is slightly more complicated.  See Section 2.10 of Washington for details.

{{{id=65|

///
}}}