All published worksheets from http://sagenb.org
Image: ubuntu2004
AMS Short Course: Computing with Elliptic Curves using Sage
January 2-3, 2012
Lecture 2: Elliptic Curves over Finite Fields
Kenneth A. Ribet, UC Berkeley
Some references: http://www.sagemath.org/doc/reference/sage/schemes/elliptic_curves/ell_finite_field.html and http://www.sagemath.org/doc/reference/sage/schemes/elliptic_curves/formal_group.html
This lecture is about elliptic curves over finite fields, so we should pick one. We'll start with and consider the fields with elements and with elements:
There are at least three different ways to define an elliptic curve over or : (1) we can specify the two coefficients of a short-form Weierstrass equation; (2) we can specify the five coefficients of a long-form Weierstrass equation; (3) we can specify a -invariant and let sage pick a curve with that -invariant.
Sage will "graph" elliptic curves over finite fields, but the resulting image may not add much to your day.
Even when working over finite fields, our mental image of an elliptic curve will tend to be like the picture below:
This is the curve that I am wearing.
I will return to , and in a couple of minutes, but first I want to look at a fourth curve, which I'll call , and find a single non-zero point on this curve "by hand."
I am fond of the prime number 144169 for two reasons. First, it's the discriminant of the Hecke algebra associated to the space of cusp forms of weight 24 on . Second, it's the concatenation of and .
The group of rational points on this curve is cyclic of order $2^3 \cdot 19 \cdot 947$.
If , the RHS of the definining equation for is 3, which is a square mod 144169. Can we find a square root of 3 mod 144169? Cipolla's algorithm, which I will explain at the end of the talk, outputs 79896 as a square root of 3.
We were able to find a generator for the group of rational points of simply by messing around. The a priori probability for success was a bit larger than 0.47:
End of interlude. Now let's go back to the three original curves and compute some of their invariants.
Note that happens to be the unique supersingular -invariant in characteristic 23, other than and , which are supersingular because is mod 3 and mod 4, respectively. It's serendipitous that we stumbled on the -invariant 19 by entering 1 and 2 as the coefiicients of our short Weierstrass equation.
If is the trace of Frobenius of a curve , the number of points of over is . Once we know , we can compute the number of points of over any finite extension of . In particular, the number of points of over is .
We can check this in all three cases, but let's just choose one case---say the middle one.
Sage takes great pleasure in computing the abelian group structure of groups of points on an elliptic curve over a finite field.
What happens over ?
So has two "independent" points of order 16; we can take the Weil pairing of these two points to get a 16th root of unity in :
To check that this element is indeed a 16th root of unity, it suffices to check that its eighth power is .
If we exchange and , the value of the Weil pairing is inverted:
Isogenies
We'll divide by a cyclic subgroup of order 32 defined over :
Over finite fields, isogenous curves have the same number of elements.
Automorphisms
A "generic" curve has only as its group of automorphisms. The curves with and have actions of and , respectively.
Embedding degree
At this point, we can fool around a bit with some large primes, just to show that sage does not choke on large numbers. The example here is from an article by David Freeman, a mathematical cryptographer who is now at Stanford.
In other words, is a large prime, in fact a 252-bit prime:
In other words, this curve has a group of rational points that is (cyclic) of prime order; we're calling the order. For Freeman, the striking fact about this example is that you can get the full group to be rational by passing to a relatively small extension of the base field (the field with elements):
In other words, if we pass to a degree-10 extension of the base field, we force all the -division points on the curve to become rational.
The fact that the ratio is an integer means that does divide the group of points on with coordinates in the large field.
The fact that the ratio is an integer means that does divide the group of points on with coordinates in the large field. As you are about to see, it is easy to find one point of order on . Finding a second independent point is a computational challenge that I haven't attempted.
Trying to run the following command will get us into a computation for which I can't estimate the "arrival time." Therefore, we won't go there!
Supersingular -invariants in characteristic 103
Formal groups
The group law attached to a formal group is a power series in two variables, called and by sage.
Square roots mod
The problem is this: if is a non-zero integer mod , it's easy to see whether is a square mod by computing mod : the result is if and only if is a square. Suppose it is? How do we find a square root of ? There's an interesting algorithm, Cipolla's algorithm http://en.wikipedia.org/wiki/Cipolla's_algorithm, that solves the problem. I learned about it from my colleague Matt Baker. It's easy to implment in sage.
The method is as follows: take random values of until you find a such that is a non-square. To , adjoin a square root of ; call it . Then is a square root of .
Thus 11 is a square mod . Can we find its square root?
The valiue wasn't hard to find: I tried until I got to 7.
In other words, the algorithm outputs 77590393 as a square root of 11 mod . We should check the result!
Fin