3914.sagews

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 $p=23$ and consider the fields with $p$ elements and with $p^2$ elements:

p=23; k=GF(p); K.<a> = GF(p^2)

p; k ; K

23 Finite Field of size 23 Finite Field in a of size 23^2

a.minimal_polynomial()

x^2 + 21*x + 5

There are at least three different ways to define an elliptic curve over $k$ or $K$: (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 $j$-invariant and let sage pick a curve with that $j$-invariant.

E1 = EllipticCurve(k, [1,2]); E2 = EllipticCurve(k,[1,2,3,4,5]); E3 = EllipticCurve(j=k(2904)) ; E1; E2; E3

Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 23 Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 23 Elliptic Curve defined by y^2 = x^3 + 15*x + 7 over Finite Field of size 23

Sage will "graph" elliptic curves over finite fields, but the resulting image may not add much to your day.

EllipticCurve(GF(503),[4,4]).plot()

Even when working over finite fields, our mental image of an elliptic curve will tend to be like the picture below:

E=EllipticCurve('389a');
G=plot(E, dpi=70);
G += sum([plot(p,pointsize=100*p.height()) for p in E.gens()]);
show(G)

This is the curve that I am wearing.

I will return to $E1$, $E2$ and $E3$ in a couple of minutes, but first I want to look at a fourth curve, which I'll call $E$, and find a single non-zero point on this curve "by hand."

E=EllipticCurve(GF(144169),[-1,3]); E

Elliptic Curve defined by y^2 = x^3 + 144168*x + 3 over Finite Field of size 144169

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 ${\bf SL}(2,{\bf Z})$.  Second, it's the concatenation of $12^2$ and $13^2$.

E.abelian_group()

Additive abelian group isomorphic to Z/143944 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 144168*x + 3 over Finite Field of size 144169

The group of rational points on this curve is cyclic of order $2^3 \cdot 19 \cdot 947$.

Mod(1^3 + 144168*1 + 3, 144169); kronecker(1^3 + 144168*1 + 3, 144169)

3 1

If $x=1$, the RHS of the definining equation for $E$ 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.

P=E([1,79896]); P; P.order()

(1 : 79896 : 1) 143944

We were able to find a generator for the group of rational points of $E$ simply by messing around.  The a priori probability for success was a bit larger than 0.47:

euler_phi(143944)/143944.

0.473184016006225

End of interlude.  Now let's go back to the three original curves and compute some of their invariants.

E1.j_invariant(); E2.j_invariant(); E3.j_invariant()

19 22 6

Note that $19 \equiv -4$ happens to be the unique supersingular $j$-invariant in characteristic 23, other than $j=0$ and $j=1728$, which are supersingular because $23$ is $-1$ mod 3 and mod 4, respectively.  It's serendipitous that we stumbled on the $j$-invariant 19 by entering 1 and 2 as the coefiicients of our short Weierstrass equation.

E1.is_supersingular(); E2.is_supersingular(); E3.is_supersingular()

True False False

E1.hasse_invariant(); E2.hasse_invariant(); E3.hasse_invariant()

0 17 8

E1.cardinality(); E2.cardinality(); E3.cardinality()

24 30 16

E1.trace_of_frobenius(); E2.trace_of_frobenius(); E3.trace_of_frobenius()

0 -6 8

If $t$ is the trace of Frobenius of a curve $E$, the number of points of $E$ over $k$ is $1+p-t$.  Once we know $t$, we can compute the number of points of $E$ over any finite extension of $K$.  In particular, the number of points of $E$ over $K$ is $(1+p)^2 - t^2= (1+p-t)(1+p+t)$.

(1+p-E1.trace_of_frobenius())*(1+p+E1.trace_of_frobenius()); (1+p-E2.trace_of_frobenius())*(1+p+E2.trace_of_frobenius()); (1+p-E3.trace_of_frobenius())*(1+p+E3.trace_of_frobenius())

576 540 512

We can check this in all three cases, but let's just choose one case---say the middle one.

E2.cardinality(extension_degree=2)

540

Sage takes great pleasure in computing the abelian group structure of groups of points on an elliptic curve over a finite field.

E1.abelian_group(); E2.abelian_group(); E3.abelian_group()

Additive abelian group isomorphic to Z/2 + Z/12 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 23 Additive abelian group isomorphic to Z/30 embedded in Abelian group of points on Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 23 Additive abelian group isomorphic to Z/2 + Z/8 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 15*x + 7 over Finite Field of size 23

What happens over $K$?

E1.change_ring(K).abelian_group(); E2.change_ring(K).abelian_group(); E3.change_ring(K).abelian_group()

Additive abelian group isomorphic to Z/24 + Z/24 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field in a of size 23^2 Additive abelian group isomorphic to Z/6 + Z/90 embedded in Abelian group of points on Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field in a of size 23^2 Additive abelian group isomorphic to Z/16 + Z/32 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 15*x + 7 over Finite Field in a of size 23^2

So $E3$ 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 $K$:

P,Q = E3.change_ring(K).gens(); P; Q; P.order(); Q.order()

(9*a : 6*a + 2 : 1) (4*a + 19 : 13*a + 6 : 1) 32 16

(2*P).weil_pairing(Q,16)

4*a + 17

To check that this element is indeed a 16th root of unity, it suffices to check that its eighth power is $-1\equiv22$.

(_)^8

22

If we exchange $P$ and $Q$, the value of the Weil pairing is inverted:

((2*P).weil_pairing(Q,16))*(Q.weil_pairing(2*P,16))

1

Isogenies

We'll divide $E3$ by a cyclic subgroup of order 32 defined over $K$:

E3overK = E3.change_ring(K)

phi = E3overK.isogeny(P); phi

Isogeny of degree 32 from Elliptic Curve defined by y^2 = x^3 + 15*x + 7 over Finite Field in a of size 23^2 to Elliptic Curve defined by y^2 = x^3 + (4*a+9)*x + (16*a+7) over Finite Field in a of size 23^2

Eprime = phi.codomain(); Eprime

Elliptic Curve defined by y^2 = x^3 + (4*a+9)*x + (16*a+7) over Finite Field in a of size 23^2

Eprime.is_isogenous(E3)

True

Over finite fields, isogenous curves have the same number of elements.

Eprime.cardinality()

512

Automorphisms

A "generic" curve has only $\{ \pm1\}$ as its group of automorphisms.  The curves with $j=0$ and $j=1728$ have actions of $\mu_3$ and $\mu_4$, respectively.

E1.change_ring(K).automorphisms()

[Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field in a of size 23^2 Via: (u,r,s,t) = (1, 0, 0, 0), Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field in a of size 23^2 Via: (u,r,s,t) = (22, 0, 0, 0)]

EllipticCurve(j=k(0)).automorphisms()

[Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 23 Via: (u,r,s,t) = (1, 0, 0, 0), Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 23 Via: (u,r,s,t) = (22, 0, 0, 0)]

EllipticCurve(j=K(0)).automorphisms()

[Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 23^2 Via: (u,r,s,t) = (1, 0, 0, 0), Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 23^2 Via: (u,r,s,t) = (22, 0, 0, 0), Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 23^2 Via: (u,r,s,t) = (4*a + 7, 0, 0, 0), Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 23^2 Via: (u,r,s,t) = (4*a + 8, 0, 0, 0), Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 23^2 Via: (u,r,s,t) = (19*a + 15, 0, 0, 0), Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 23^2 Via: (u,r,s,t) = (19*a + 16, 0, 0, 0)]

(19*a+16)^3

22

EllipticCurve(j=K(1728)).automorphisms()

[Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in a of size 23^2 Via: (u,r,s,t) = (1, 0, 0, 0), Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in a of size 23^2 Via: (u,r,s,t) = (22, 0, 0, 0), Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in a of size 23^2 Via: (u,r,s,t) = (11*a + 12, 0, 0, 0), Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in a of size 23^2 Via: (u,r,s,t) = (12*a + 11, 0, 0, 0)]

(12*a + 11)^2

22

F.<b>= GF(4); len(EllipticCurve(j=F(0)).automorphisms())

24

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.

q=6462310997348816962203124910505252082673338846966431201635262694402825461643; factor(q)

In other words, $q$ is a large prime, in fact a 252-bit prime:

len(q.str(2))

E=EllipticCurve(GF(q),[-3,4946538166640251374274628820269694144249181776013154863288086212076808528141])

time n=E.order(); n; is_prime(n)

In other words, this curve has a group of rational points that is (cyclic) of prime order; we're calling $n$ the order.  For Freeman, the striking fact about this example is that you can get the full group $E[n]\approx ({\bf Z}/n{\bf Z})^2$ to be rational by passing to a relatively small extension of the base field (the field with $q$ elements):

Mod(q,n).multiplicative_order()

In other words, if we pass to a degree-10 extension of the base field, we force all the $n$-division points on the curve to become rational.

time E.cardinality(extension_degree=10)/n^2

The fact that the ratio is an integer means that $n^2$ does divide the group of points on $E$ with coordinates in the large field.

The fact that the ratio is an integer means that $n^2$ does divide the group of points on $E$ with coordinates in the large field.  As you are about to see, it is easy to find one point of order $n$ on $E$.  Finding a second independent point is a computational challenge that I haven't attempted.

time E.gens()

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!

#  K.<a>= GF(q^10); E.change_ring(K).gens()

Supersingular $j$-invariants in characteristic 103

from sage.schemes.elliptic_curves.ell_finite_field import supersingular_j_polynomial

f=supersingular_j_polynomial(103); type(f)

<type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>

supersingular_j_polynomial(103).factor()

(j + 34) * (j + 69) * (j + 79) * (j + 80) * (j^2 + 63*j + 69) * (j^2 + 84*j + 73)

R.<x>=L[]

R

Univariate Polynomial Ring in x over Finite Field in c of size 103^2

f(x)

x^8 + 100*x^7 + 84*x^6 + 83*x^5 + 70*x^4 + 58*x^3 + 24*x^2 + 15*x + 64

factor(_)

(x + 34) * (x + 69) * (x + 79) * (x + 80) * (x + 40*c + 63) * (x + 46*c + 19) * (x + 57*c + 65) * (x + 63*c)

supersingular_j_polynomial(103).degree()

8

floor((103-1)/12)

8

E=EllipticCurve(j=L(-63*c))

E.is_supersingular()

True

Formal groups

G1=E1.formal_group(); G3 = E3.formal_group()

The group law attached to a formal group is a power series in two variables, called $t1$ and $t2$ by sage.

G1.group_law(15); G3.group_law(15)

t1 + O(t1^15) + (1 + 21*t1^4 + 17*t1^6 + 21*t1^8 + 7*t1^10 + 18*t1^12 + 19*t1^14 + O(t1^15))*t2 + (19*t1^3 + 5*t1^5 + 3*t1^9 + 10*t1^11 + 4*t1^13 + O(t1^15))*t2^2 + (19*t1^2 + 16*t1^4 + 8*t1^6 + t1^8 + 10*t1^10 + 16*t1^12 + 3*t1^14 + O(t1^15))*t2^3 + (21*t1 + 16*t1^3 + 16*t1^5 + 5*t1^7 + t1^9 + 18*t1^11 + 12*t1^13 + O(t1^15))*t2^4 + (5*t1^2 + 16*t1^4 + 20*t1^6 + 18*t1^8 + 7*t1^10 + 7*t1^12 + 21*t1^14 + O(t1^15))*t2^5 + (17*t1 + 8*t1^3 + 20*t1^5 + 8*t1^7 + 6*t1^9 + 4*t1^11 + 10*t1^13 + O(t1^15))*t2^6 + (5*t1^4 + 8*t1^6 + 12*t1^8 + 18*t1^10 + 15*t1^12 + 5*t1^14 + O(t1^15))*t2^7 + (21*t1 + t1^3 + 18*t1^5 + 12*t1^7 + t1^9 + 22*t1^11 + 21*t1^13 + O(t1^15))*t2^8 + (3*t1^2 + t1^4 + 6*t1^6 + t1^8 + 20*t1^10 + 6*t1^12 + 22*t1^14 + O(t1^15))*t2^9 + (7*t1 + 10*t1^3 + 7*t1^5 + 18*t1^7 + 20*t1^9 + 17*t1^11 + t1^13 + O(t1^15))*t2^10 + (10*t1^2 + 18*t1^4 + 4*t1^6 + 22*t1^8 + 17*t1^10 + 13*t1^12 + O(t1^15))*t2^11 + (18*t1 + 16*t1^3 + 7*t1^5 + 15*t1^7 + 6*t1^9 + 13*t1^11 + 8*t1^13 + O(t1^15))*t2^12 + (4*t1^2 + 12*t1^4 + 10*t1^6 + 21*t1^8 + t1^10 + 8*t1^12 + 14*t1^14 + O(t1^15))*t2^13 + (19*t1 + 3*t1^3 + 21*t1^5 + 5*t1^7 + 22*t1^9 + 14*t1^13 + O(t1^15))*t2^14 + O(t2^15) t1 + O(t1^15) + (1 + 16*t1^4 + 2*t1^6 + 10*t1^8 + 11*t1^10 + 6*t1^12 + t1^14 + O(t1^15))*t2 + (9*t1^3 + 6*t1^5 + 8*t1^9 + 19*t1^11 + 22*t1^13 + O(t1^15))*t2^2 + (9*t1^2 + 10*t1^4 + 6*t1^6 + 18*t1^8 + 11*t1^10 + 19*t1^12 + 18*t1^14 + O(t1^15))*t2^3 + (16*t1 + 10*t1^3 + 12*t1^5 + 21*t1^7 + 18*t1^9 + 7*t1^11 + 20*t1^13 + O(t1^15))*t2^4 + (6*t1^2 + 12*t1^4 + 15*t1^6 + 11*t1^8 + 4*t1^10 + t1^12 + 10*t1^14 + O(t1^15))*t2^5 + (2*t1 + 6*t1^3 + 15*t1^5 + t1^7 + 10*t1^9 + 22*t1^11 + O(t1^15))*t2^6 + (21*t1^4 + t1^6 + 20*t1^8 + 19*t1^10 + 12*t1^12 + 16*t1^14 + O(t1^15))*t2^7 + (10*t1 + 18*t1^3 + 11*t1^5 + 20*t1^7 + 18*t1^9 + 5*t1^11 + 6*t1^13 + O(t1^15))*t2^8 + (8*t1^2 + 18*t1^4 + 10*t1^6 + 18*t1^8 + 21*t1^10 + 15*t1^12 + O(t1^15))*t2^9 + (11*t1 + 11*t1^3 + 4*t1^5 + 19*t1^7 + 21*t1^9 + 7*t1^11 + t1^13 + O(t1^15))*t2^10 + (19*t1^2 + 7*t1^4 + 22*t1^6 + 5*t1^8 + 7*t1^10 + 21*t1^12 + 2*t1^14 + O(t1^15))*t2^11 + (6*t1 + 19*t1^3 + t1^5 + 12*t1^7 + 15*t1^9 + 21*t1^11 + 4*t1^13 + O(t1^15))*t2^12 + (22*t1^2 + 20*t1^4 + 6*t1^8 + t1^10 + 4*t1^12 + 13*t1^14 + O(t1^15))*t2^13 + (t1 + 18*t1^3 + 10*t1^5 + 16*t1^7 + 2*t1^11 + 13*t1^13 + O(t1^15))*t2^14 + O(t2^15)

G0=EllipticCurve(j=F(0)).formal_group(); G0

Formal Group associated to the Elliptic Curve defined by y^2 + y = x^3 over Finite Field in b of size 2^2

G0.mult_by_n(2)

t^4 + O(t^10)

G1.mult_by_n(23,prec=30)

O(t^30)

G3.mult_by_n(23, prec=30)

8*t^23 + O(t^30)

Square roots mod $p$

The problem is this: if $a$ is a non-zero integer mod $p$, it's easy to see whether $a$ is a square mod $p$ by computing $a^{(p-1)/2}$ mod $p$: the result is $+1$ if and only if $a$ is a square.  Suppose it is?  How do we find a square root of $a$?  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 $t$ until you find a $t$ such that $t^2-a$ is a non-square.  To ${\bf F}_p$, adjoin a square root of $t^2-a$; call it $\omega$.  Then $(a+\omega)^{(p+1)/2}$ is a square root of $a$.

p=1234567891; a= 11; kronecker(a,p)

1

Thus 11 is a square mod $p=1234567891$.  Can we find its square root?

t=7; kronecker(t^2-a,p)

-1

The valiue $t=7$ wasn't hard to find: I tried $t=1,\ldots$ until I got to 7.

R.<x> = PolynomialRing(GF(p)); R

Univariate Polynomial Ring in x over Finite Field of size 1234567891

t=7; b=(t^2-a)%p; S.<omega> = R.quo((x^2-b)); S

Univariate Quotient Polynomial Ring in omega over Finite Field of size 1234567891 with modulus x^2 + 1234567853

squareroot= (t+omega)^((p+1)/2); squareroot

77590393

In other words, the algorithm outputs 77590393 as a square root of 11 mod $p$.  We should check the result!

77590393^2%p

\newcommand{\Bold}[1]{\mathbf{#1}}11

Fin