# distortion map phi(x,y) = (-x, i*y) where i = sqrt(-1)

[Question updated to reflect progress]

This question relates to implementing a distortion map between a finite field and an extension field in the context of bilinear pairings on super singular curves.

The numerical example comes from Ben Lynn's thesis[1], from p. 38-49, and involves subject matter discussed on p. 54.

The math context is as follows:

Given:

```
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)
the pairing function f(...) can be called on p, q, in G by applying the distortion map on q, thus
m = f(p, phi(q))
```

For example:

```
if p = G(25, 50),
let : q = phi(25,30) = (-25, 30 *i)
m = f(p,q) = f((25,30), (-25, 30*i)) = 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 performing point conversion and invoking the weil pairing.

I have attempted variations on the following simple approach (discussion of background appears in comments, below):

```
F59 = GF(59)
E59 = EllipticCurve(F59, [1,0])
F59sq.<u> = GF(59)[i]
E59sq = EllipticCurve(F59sq, [1,0])
def phi(x,y):
return ( - x, y * u)
p = E59(25,30)
q = phi(p[0],p[1])
#conversion problem:
q = E59sq(F59sq(q[0]), F59sq(q[1]))
p.weil_pairing(q, 5)
```

The problem appears in the pairing function, with the point created on E59sq.

I receive the following error:

```
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-3-1d9ffe6c337c> in <cell line: 12>()
10
11 q = E59sq(F59sq(q[Integer(0)]), F59sq(q[Integer(1)]))
---> 12 p.weil_pairing(q, Integer(5))
~/mambaforge/envs/sage/lib/python3.9/site-packages/sage/schemes/elliptic_curves/ell_point.py in weil_pairing(self, Q, n, algorithm)
1621
1622 if Q.curve() is not E:
-> 1623 raise ValueError("points must both be on the same curve")
1624
1625 if algorithm is None:
ValueError: points must both be on the same curve
```

Question 1: Can someone explain the error, and assist in making the demonstration 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, but somehow it seems to have potential. Can someone explain this construction, and perhaps how it can be applied to the example above?

Question 3: If you were approaching this problem and sought a balance of "communicative code", and idomatic sagemath", how would you approach it?

Thanks in advance.

[1] crypto.stanford.edu/pbc/thesis.pdf

[2]doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/ell_point.html

Thanks Max. I have edited the code above to fix it, and add your suggestion. When I run it now it has a new error ("points must be on the same curve"). Running it a second time results in a different error ("PariError: I already exists with incompatible valence")

I wonder, would it be best to keep away from

`i`

and perhaps use a different label? As well, if I may ask -- how would the code best be implemented for goals of being clear as well as idiomatic in sagemath?Thanks again

Thanks I changed the label. It makes the 'valence' error go away. Still now, there is the "points must be on the same curve" error. Why is this occuring, and what should I do to fix it?

Thank you, Max, I have updated the question.

The error is what the message says:

`p`

and`q`

are not points of the same curve. Indeed`p`

is a point of`E59`

and`q`

is a point of`E59sq`

. Convert`p`

to a point of`E59sq`

. And, please, fix the missing parentheses in your code.Shouldn't it be simply?

It produces an error

`PariError: I already exists with incompatible valence`

, which may be a real question here.