Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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

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

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

I have questions about how to implement a distortion map between a finite field and an extension feild field in the context of bilinear pairings on super singular curves.

From: Ben Lynn's thesis, [1] 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*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.htmlcrypto.stanford.edu/pbc/thesis.pdf

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

click to hide/show revision 3
retagged

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

I have questions about how to implement a distortion map between a finite field and an extension field in the context of bilinear pairings on super singular curves.

From: [1] on p38 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)

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 ( - 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.stanford.edu/pbc/thesis.pdf

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

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

I have questions about how to implement a distortion map between a finite field and an extension field in the context of bilinear pairings on super singular curves.

From: [1] on p38 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)

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> F59sq.<u> = GF(59^2)
E59sq = EllipticCurve(F59, [1,0])
def phi(x,y):
    return ( - 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.stanford.edu/pbc/thesis.pdf

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

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

I have questions about how to implement [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.

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

The math context is as follows:

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)

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: approach (discussion of background appears in comments, below):

F59 = GF(59)
E59 = EllipticCurve(F59, [1,0])
F59sq.<u> = GF(59^2)
E59sq = EllipticCurve(F59, [1,0])
def phi(x,y):
    return ( - 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:receive the following error:

ValueError: 30*i ---------------------------------------------------------------------------
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 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
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: How can this be made to 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. I works, but somehow it seems to have not found much discussion on this technique in the documentation. 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

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: 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)

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 (discussion of background appears in comments, below):

F59 = GF(59)
E59 = EllipticCurve(F59, [1,0])
F59sq.<u> = GF(59^2)
E59sq = EllipticCurve(F59, [1,0])
def phi(x,y):
    return ( - 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 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

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: 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)

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 (discussion of background appears in comments, below):

F59 = GF(59)
E59 = EllipticCurve(F59, [1,0])
F59sq.<u> = GF(59^2)
E59sq = EllipticCurve(F59, [1,0])
def phi(x,y):
    return ( - x, y * i)

p = E59(25,30)
q = phi(p[0],p[1])
#conversion problem:
q =  F59sq(F59sq(q[0], E59sq(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 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

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: 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)

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 (discussion of background appears in comments, below):

F59 = GF(59)
E59 = EllipticCurve(F59, [1,0])
F59sq.<u> = GF(59^2)
E59sq = EllipticCurve(F59, [1,0])
def phi(x,y):
    return ( - x, y * i)

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 I run into is at the step where appears in the pairing function, after I try to create a point 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

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: 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)

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 (discussion of background appears in comments, below):

F59 = GF(59)
E59 = EllipticCurve(F59, [1,0])
F59sq.<u> = GF(59^2)
E59sq = EllipticCurve(F59, [1,0])
def phi(x,y):
    return ( - x, y * i)
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, after I try to create a point 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

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: 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)

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 (discussion of background appears in comments, below):

F59 = GF(59)
E59 = EllipticCurve(F59, [1,0])
F59sq.<u> = GF(59^2)
E59sq = EllipticCurve(F59, [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, after I try to create a 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

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: 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)
 

For example:

q = phi(25,30) = (-25, 30 *i)

*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 (discussion of background appears in comments, below):

F59 = GF(59)
E59 = EllipticCurve(F59, [1,0])
F59sq.<u> = GF(59^2)
E59sq = EllipticCurve(F59, [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

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 pq, 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*1) = 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 performing point conversion and calling 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^2)
E59sq = EllipticCurve(F59, [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

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 pq, 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*1) 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^2)
E59sq = EllipticCurve(F59, [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

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^2)
E59sq = EllipticCurve(F59, [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])
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

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^2)
GF(59)[i]
E59sq = EllipticCurve(F59, [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

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(F59, 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