SageMath: defining class of functions on Elliptic Curves

asked 2020-06-25 22:00:00 -0500

fagui gravatar image

updated 2020-07-02 17:36:22 -0500

slelievre gravatar image

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/pairi...

EDIT

My question hasn't attracted much interest so let me give a more concrete example.

Define the following:

# Code related to the example in Costello
q = 47
F = GF(q)
R.<x> = F[]
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 divides 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):
    lamda = (Q[1] - P[1]) / (Q[0] - P[0])
    c = P[1] - lamda * P[0]
    l = (y - (lamda * x + c))
    v = (x - (lamda^2 - P[0] - P[1]))
    return l / v

I would have hoped for fADD_(P, Q, x, y) to return a rational function in x, y.

Instead it raises the following error:

---------------------------------------------------------------------------
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 = <object>cursor.value

KeyError: (Finite Field in u of size 47^4, Symbolic Ring, <built-in
function mul>)

During handling of the above exception, another exception occurred:

TypeError                                 Traceback (most recent call
last) <ipython-input-54-7441affd269c> in <module>()
----> 1 fADD_(P,Q,x,y)

<ipython-input-48-20f93738e654> 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_da*P[Integer(0)]
----> 4     l =(y-(lamb_da*x+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 (<Element>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>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 = (<Parent>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 (<ModuleElement>a)._lmul_(<Element>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
edit retag flag offensive close merge delete

Comments

The example as given doesn't give an error. If I execute fADD_(P,Q,x,y), I get an error because y is not defined. The error you describe suggests you may have executed var('y') before. I don't know what y should be. Perhaps something like the code below?

Ea=E.affine_patch(2)
k=Ea.coordinate_ring().fraction_field()
xbar,ybar=k.gens()
fADD_(P,Q,xbar,ybar)
nbruin gravatar imagenbruin ( 2020-06-26 09:58:21 -0500 )edit