I have questions about how to implement a distortion map between a finite field and an extension feild in the context of bilinear pairings on super singular curves.
From: Ben Lynn's thesis, on p38 [1] Given: curve E: Y^2 = X^3 + X over F59 G = {(25, 30), (35,31), (35, 28), (25, 29), 0 }, the 5-torsion group in F59 phi(x,y) = (-x, y * i ), where i = sqrt(-1) phi(25,30) = (-25, 30 i) weil_pairing((25,30), (-25, 301)) = 46 + 56*i
The distortion map can be verified to work:
LHS: Y^2 = (30*i)^2 = 30^2 * i^2 = 900 * (-1) mod 59 = 44
RHS = (-25)^3 -25 = -15625 - 25 (mod 59) = 44
LHS == RHS.
I'd like to implement and extend this example in sagemath, including the point conversion and calling the weil pairing.
I have attempted variations on the following simple approach:
F59 = GF(59)
E59 = EllipticCurve(F59, [1,0])
F59sq.<i> = GF(59^2)
E59sq = EllipticCurve(F59, [1,0])
def phi(x,y):
return E59sq( - x, y * i)
p = E59(25,30)
q = phi(p[0],p[1])
#conversion problem:
q = F59sq(F59sq(q[0], F59sq(q[1])
p.weil_pairing(q, 5)
The problem I run into is at the step where I try to create a point on E59sq.
I receive:
ValueError: 30*i is not in the image of (map internal to coercion system -- copy before use)
Ring morphism:
From: Finite Field of size 59
To: Finite Field in i of size 59^2
Question 1: How can this be made to work ?
Question 2: The sagemath documentation [2] uses an approach such as:
phi=Hom(F,Fx)(F.gen().minpoly().roots(Fx)[0][0])
Px=Ex(phi(P.xy()[0]),phi(P.xy()[1]))
I am not sure how this works. I have not found much discussion on this technique in the documentation. Can someone explain this construction, and perhaps how it can be applied to the example above?
[1] crypto dot stanford dot edu/pbc/thesis.pdf
[2]doc dot sagemath dot org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/ell_point.html