1
$\begingroup$

In SageMath,

I would like to manipulate rational functions on elliptic curves (defined on finite fields). For example, for $P = (x,y)$ on some curve $E$

$$f = x+y-12$$ $$g = \frac{x+y-3}{(x-3)^2} $$ etc.

Is there a natural class ?

I am looking to make a toy example with pairings, so I need to define stuff like $$P \rightarrow f_P$$ where $$f_P:Q \rightarrow f_P(Q)$$ is a function

I can't see how to do that, and I'm able to make computations if I define

def f (P,Q):
   ....

but I can only compute the values taken by the function $f_P$, I cannot "see" the function $f_P$. Basically I'm trying as an exercise to re-write the following Magma code to SageMath:

http://www.craigcostello.com.au/pairings/beginners/5-3-1-TateWeilMiller.txt

EDIT: my question hasn't attracted much interest so i'm going to give a more concrete example:

# this is the beginning of the code related to the example in Costello
q=47
F = GF(q)
R.<x> = F[] ; R
F4.<u>= F.extension(x^4-4*x^2+5) 
a = 21 ; b= 15
E = EllipticCurve(F4,[a,b])
r=17
k=4 
(q^4-1) % r # r=17 is a divisor of q^4 - 1 = 47^4 - 1
P = E([45,23])
P.order()
h = E.cardinality() / r^2
O = E(0)
Q = E([5*u^3 + 37*u + 13,7*u^3 + 45*u^2 + 10*u + 7])

def fADD_(P,Q,x,y):
    lamb_da=(Q[1]-P[1])/(Q[0]-P[0])
    c =P[1]-lamb_da*P[0]
    l =(y-(lamb_da*x+c))
    v =(x-(lamb_da^2-P[0]-P[1]))
    return (l/v)

fADD_(P,Q,x,y) will return an error while i would have liked it to return a rational function in x,y

--------------------------------------------------------------------------- KeyError Traceback (most recent call last) /Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:9946)() 1195 try: -> 1196 action = self._action_maps.get(xp, yp, op) 1197 except KeyError:

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/coerce_dict.pyx in sage.structure.coerce_dict.TripleDict.get (build/cythonized/sage/structure/coerce_dict.c:7917)() 1327
if not valid(cursor.key_id1): -> 1328 raise KeyError((k1, k2, k3)) 1329 value = cursor.value

KeyError: (Finite Field in u of size 47^4, Symbolic Ring, )

During handling of the above exception, another exception occurred:

TypeError Traceback (most recent call last) in () ----> 1 fADD_(P,Q,x,y)

in fADD_(P, Q, x, y) 2 lamb_da=(Q[Integer(1)]-P[Integer(1)])/(Q[Integer(0)]-P[Integer(0)]) 3 c =P[Integer(1)]-lamb_daP[Integer(0)] ----> 4 l =(y-(lamb_dax+c)) 5 v =(x-(lamb_da**Integer(2)-P[Integer(0)]-P[Integer(1)])) 6 return (l/v)

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element.mul (build/cythonized/sage/structure/element.c:12034)() 1515
return (left).mul(right) 1516 if BOTH_ARE_ELEMENT(cl): -> 1517 return coercion_model.bin_op(left, right, mul) 1518 1519 cdef long value

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:9996)() 1196
action = self._action_maps.get(xp, yp, op) 1197 except KeyError: -> 1198 action = self.get_action(xp, yp, op, x, y) 1199 if action is not None: 1200 if (action)._is_left:

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.get_action (build/cythonized/sage/structure/coerce.c:16783)() 1725
except KeyError: 1726 pass -> 1727 action = self.discover_action(R, S, op, r, s) 1728 action = self.verify_action(action, R, S, op) 1729
self._action_maps.set(R, S, op, action)

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.discover_action (build/cythonized/sage/structure/coerce.c:18201)() 1856 """ 1857 if isinstance(R, Parent): -> 1858 action = (R).get_action(S, op, True, r, s) 1859 if action is not None: 1860 return action

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.get_action (build/cythonized/sage/structure/parent.c:19901)() 2475
action = self.get_action(S, op, self_on_left) 2476 if action is None: -> 2477 action = self.discover_action(S, op, self_on_left, self_el, S_el) 2478 2479 if action is not None:

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.discover_action (build/cythonized/sage/structure/parent.c:20878)() 2554

detect actions defined by rmul, lmul, act_on, and acted_upon methods 2555 from .coerce_actions import

detect_element_action -> 2556 action = detect_element_action(self, S, self_on_left, self_el, S_el) 2557 if action is not None: 2558 return action

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/coerce_actions.pyx in sage.structure.coerce_actions.detect_element_action (build/cythonized/sage/structure/coerce_actions.c:5026)() 215 if isinstance(x, ModuleElement) and isinstance(y, Element): 216 try: --> 217 return (RightModuleAction if X_on_left else LeftModuleAction)(Y, X, y, x) 218 except CoercionException as msg: 219 _record_exception()

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/coerce_actions.pyx in sage.structure.coerce_actions.ModuleAction.init (build/cythonized/sage/structure/coerce_actions.c:6778)() 361 if not isinstance(g, Element) or not isinstance(a, ModuleElement): 362 raise CoercionException("not an Element acting on a ModuleElement") --> 363 res = self.act(g, a) 364 if parent(res) is not the_set: 365 # In particular we will raise an error if res is None

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/categories/action.pyx in sage.categories.action.Action.act (build/cythonized/sage/categories/action.c:4115)() 213 5*x 214 """ --> 215 return self._act_convert(g, x) 216 217 def invert(self):

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/categories/action.pyx in sage.categories.action.Action._act_convert (build/cythonized/sage/categories/action.c:3759)() 169 if parent(x) is not U: 170 x = U(x) --> 171 return self.act(g, x) 172 173 cpdef act(self, g, x):

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/coerce_actions.pyx in sage.structure.coerce_actions.RightModuleAction.act (build/cythonized/sage/structure/coerce_actions.c:8600)() 629 g = <Element?>self.connecting.call(g) 630 if self.extended_base is not None: --> 631 a = <ModuleElement?>self.extended_base(a) 632 return (a).lmul(g) # a * g 633

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.call (build/cythonized/sage/structure/parent.c:9218)() 898 if mor is not None: 899 if no_extra_args: --> 900 return mor.call(x) 901 else: 902 return mor._call_with_args(x, args, kwds)

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique.call (build/cythonized/sage/structure/coerce_maps.c:4556)() 159 print(type(C), C) 160 print(type(C._element_constructor), C._element_constructor) --> 161 raise 162 163 cpdef Element _call_with_args(self, x, args=(), kwds={}):

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique.call (build/cythonized/sage/structure/coerce_maps.c:4448)() 154 cdef Parent C = self._codomain 155 try: --> 156 return C._element_constructor(x) 157 except Exception: 158 if print_warnings:

/Applications/SageMath-9.1.app/Contents/Resources/sage/local/lib/python3.7/site-packages/sage/symbolic/ring.pyx in sage.symbolic.ring.SymbolicRing.element_constructor (build/cythonized/sage/symbolic/ring.cpp:6648)() 377 elif isinstance(x, (RingElement, Matrix)): 378 if x.parent().characteristic(): --> 379 raise TypeError('positive characteristic not allowed in symbolic computations') 380 exp = x 381 elif isinstance(x, Factorization):

TypeError: positive characteristic not allowed in symbolic computations

$\endgroup$
5
  • $\begingroup$ Certainly the keyword here is probably "function field" since your rational functions live inside $\bar{\mathbb{F}_p}(E)$, although I am not sure how they are implemented in Sage, or how to evaluate them at points. $\endgroup$
    – Mummy the turkey
    Jun 23, 2020 at 10:45
  • $\begingroup$ I don't understand that piece of Magma, so I can't tell exactly what you want. If you just want to take the function $f(P,Q)$ and fix $P$ to get a function $f_P(Q)$ then in Sage you can do something like f_P = lambda Q : f(P,Q). $\endgroup$
    – user208649
    Jun 24, 2020 at 1:11
  • $\begingroup$ stupid example $f_P$ could be $Q \rightarrow P+Q$ $\endgroup$
    – Fagui Curtain
    Jun 24, 2020 at 1:45
  • $\begingroup$ it's like doing a partial evaluation of a function of 2 variables F(X,Y). if you fix $X=X_0$ you are left with a function $F_{X_0}(Y)$ i am interested in seeing the details of $F_{X_0}$ because i want to manipulate the coefficients to create new functions $\endgroup$
    – Fagui Curtain
    Jun 24, 2020 at 1:53
  • $\begingroup$ I don't know what you mean by "see the details". If you have $f(P,Q) = f(P_1,P_2,Q_1,Q_2)$ defined as a rational function in sage, then to figure out $f_P$ as a rational function, you can just evaluate $f(P_1,P_2,x,y)$ where $x,y$ are two variables. It will then print out what you want, I think. $\endgroup$
    – user208649
    Jun 24, 2020 at 4:48

1 Answer 1

Reset to default
0
$\begingroup$

It was hard (for me) to find the starting point of the question. You are working i a concrete situation and the task is clear, but i had to guess which is the point of the question. (We want to "translate" some magma code to sage? Or we want to correct the sage code snippet only? Or the question is the reason for the long traceback information?)

This answer is "making the sage code work". (If something else is the subject of the question, please edit.) Note first that the given code is not complete, well y is not defined. This may be also the reason for the error. (If it is a variable, or it is not "married" structurally with x, then i would expect such errors.)

The following piece of code worked for me:

p = 47
F = GF(p)
R.<x>  = PolynomialRing(F)
F4.<u> = GF(p^4, modulus=x^4 - 4*x^2 + 5)

a, b = 21, 15
E = EllipticCurve(F4, [a,b])
print(f"Working with the elliptic curve E:\n{E}")

r = 17
k = 4
print("Is r = {} dividing p^4 - 1 = {}? {}"
      .format(r, p^4 - 1, r.divides(p^4 - 1)))

P = E.point([45, 23])
print(f"The order of the point {P.xy()} is {P.order()}")

h = E.cardinality() / r^2
O = E(0)
Q = E.point([5*u^3 + 37*u + 13, 7*u^3 + 45*u^2 + 10*u + 7])

R.<x,y> = PolynomialRing(F)
# or F4 instead of F, to avoid structural coerce

def myadd(P, Q, x, y):
    m = (Q[1] - P[1]) / (Q[0] - P[0])
    c = P[1] - m*P[0]
    return (y - (m*x+c)) / (x - (m^2 - P[0] - P[1]))

myadd(P, Q, x, y)

(Please try to give a readable shape to the code, i also break pep8 rules, but spaces make reading (and error searching) easier.)

The above gave me:

Working with the elliptic curve E:
Elliptic Curve defined by y^2 = x^3 + 21*x + 15
    over Finite Field in u of size 47^4
Is r = 17 dividing p^4 - 1 = 4879680? True
The order of the point (45, 23) is 17
((5*u^3 + 22*u^2 + 2*u - 4)*x 
    + y + (10*u^3 - 3*u^2 + 4*u + 16))
/
(x + (12*u^3 - 4*u^2 - 12*u + 17))

(... manually rearrange to better fit the stackexchange format.)

And indeed, the result of myadd(P, Q, x, y) is a rational function in x and y, defined over F4.

(I will try to see what happens in the other code, but i do not have magma on this own linux machine.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .