AMS Short Course -- K. Ribet

145 days ago by ribet

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
23
Finite Field of size 23
Finite Field in a of size 23^2
a.minimal_polynomial() 
        
x^2 + 21*x + 5
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
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
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
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
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
(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
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
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
True
False
False
E1.hasse_invariant(); E2.hasse_invariant(); E3.hasse_invariant() 
        
0
17
8
0
17
8
E1.cardinality(); E2.cardinality(); E3.cardinality() 
        
24
30
16
24
30
16
E1.trace_of_frobenius(); E2.trace_of_frobenius(); E3.trace_of_frobenius() 
        
0
-6
8
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
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
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
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
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
(9*a : 6*a + 2 : 1)
(4*a + 19 : 13*a + 6 : 1)
32
16
(2*P).weil_pairing(Q,16) 
        
4*a + 17
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
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
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
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
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
True

Over finite fields, isogenous curves have the same number of elements.
Eprime.cardinality() 
        
512
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)]
[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)]
[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)]
[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
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)]
[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
22
F.<b>= GF(4); len(EllipticCurve(j=F(0)).automorphisms()) 
        
24
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'>
<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)
(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
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
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)
(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
8
floor((103-1)/12) 
        
8
8
E=EllipticCurve(j=L(-63*c)) 
       
E.is_supersingular() 
        
True
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)
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
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)
t^4 + O(t^10)
G1.mult_by_n(23,prec=30) 
        
O(t^30)
O(t^30)
G3.mult_by_n(23, prec=30) 
        
8*t^23 + O(t^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
1

Thus 11 is a square mod p=1234567891.  Can we find its square root?
t=7; kronecker(t^2-a,p) 
        
-1
-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
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
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
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
\newcommand{\Bold}[1]{\mathbf{#1}}11

Fin