We create finite fields by passing their cardinality
Fp = GF(11)
Fp
Finite Field of size 11
Fq = GF(11^2)
Fq
Finite Field in z2 of size 11^2
For extension fields, the generator is obtained with the .gen()
function.
z = Fq.gen()
z
z2
z^120
1
Same thing in one go
K.<t> = GF(next_prime(2^128)^2)
K
Finite Field in t of size 340282366920938463463374607431768211507^2
Curves over $ℚ$
E = EllipticCurve([-10,10])
E
Elliptic Curve defined by y^2 = x^3 - 10*x + 10 over Rational Field
E.plot()
Cuvers over other fields
F = EllipticCurve(GF(11), [1, 0])
F
Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11
F.order()
12
F.cardinality()
12
F.points()
[(0 : 0 : 1), (0 : 1 : 0), (5 : 3 : 1), (5 : 8 : 1), (7 : 3 : 1), (7 : 8 : 1), (8 : 5 : 1), (8 : 6 : 1), (9 : 1 : 1), (9 : 10 : 1), (10 : 3 : 1), (10 : 8 : 1)]
P = F.random_point()
P
(9 : 1 : 1)
P.order()
6
Group structure
F.abelian_group()
Additive abelian group isomorphic to Z/12 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11
g = F.gens()[0]
g
(8 : 6 : 1)
g.order()
12
Construct an isogeny with given kernel
origin = 6*g
origin
(0 : 0 : 1)
F.point([0,0])
(0 : 0 : 1)
I = F.isogeny(origin)
I
Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11 to Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11
I.rational_maps()
((x^2 + 1)/x, (x^2*y - y)/x^2)
FF = I.codomain()
FF
Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11
FF.abelian_group()
Additive abelian group isomorphic to Z/6 + Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11
FF.plot()
The same example, over the rationals
E = EllipticCurve([1,0])
P = E.lift_x(0)
P
(0 : 0 : 1)
P.order()
2
J = E.isogeny(P)
EE = J.codomain()
EE
Elliptic Curve defined by y^2 = x^3 - 4*x over Rational Field
In (very) limited cases, Sage can compute the isogeny given the image curve and the degree
JJ = E.isogeny(None, codomain=EE, degree=2)
J == JJ
True
Implement the (naive) Diffie-Helman key exchange scheme with elliptic curves.
Choose a prime $p$. Take curves at random over $𝔽_p$ until you find one with prime order.
Suggestion: For a start, take $p$ of ~60 bits. When your code works well enough you can try 160 bits (it may take a few minutes to find a curve)
Write a function to sample secret keys, and a function to produce public keys. Perform the key exchnage and verify that Alice and Bob obtain the same key.
Implement Lenstra's factoring method. See the lecture notes, Section 5.
Note: Sage has limited support for curves over $ℤ/Nℤ$, just enough to implement ECM.
Implement the Couveignes-Lercier method for generating irreducible polynomials. See the lecture notes, Section 8.
Note: Sage has limited support for curves over $ℤ/Nℤ$, just enough to implement ECM.