ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 26 Jun 2020 05:00:00 +0200SageMath: defining class of functions on Elliptic Curveshttps://ask.sagemath.org/question/52223/sagemath-defining-class-of-functions-on-elliptic-curves/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 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
computationsfaguiFri, 26 Jun 2020 05:00:00 +0200https://ask.sagemath.org/question/52223/Elliptic Curve Twisthttps://ask.sagemath.org/question/45530/elliptic-curve-twist/Hello, I am trying to compute the quadratic twist for an example of an Elliptic curve defined over a GF(p^8) Field:
With
p=3351951982486667453837338848452726606028033606935065896469552348842908133596080151967071453287452469772970937967942438575522391344438242727636910570385409
and an Elliptic curve defined as:
E = ElllipticCurve(GF(p),[1,0])
given the extensions:
F2.<i> = GF(p^2, modulus=x^2 + 11)
F4.<j> = GF(p^4, modulus=x^4 + 11)
F8.<k> = GF(p^8, modulus=x^8 + 11)
I am trying to compute a twist of the elliptic curve defined over F8, of the twist equation form: y^2=x^3+a w^4 x, while a=1, and w satisfies the following: $w\in F_{p^8}$ and $w^4 \in F_{p^2}$, $w^2 \in F_{p^4}$ and $w^3 \in F_{p^{8}} \setminus F_{p^{4}}$
Is there any sage command that would help with this problem ?
Another way but I didn't know how to write it in sage: {1,w,w^2,w^3} are the basis of $F_{p^8}$ as a vector space over $F_{p^{2}}$.
Thanks in advance.JosephThu, 21 Feb 2019 17:03:56 +0100https://ask.sagemath.org/question/45530/Iterate over multivariate polynomials over finite fieldshttps://ask.sagemath.org/question/50136/iterate-over-multivariate-polynomials-over-finite-fields/Say we have a finite field, e.g. $F_4$, and consider the $n$-ary polynomials $R=F_4[x_1,\dots,x_n]$ over this field.
I want to iterate over all these polynomials in $R$. Since the polynomials are over a finite field there are only finitely many different polynomials (considered as functions $F_4^n \to F_4$). How can I do this?
For $n=1$ I could do
R.<x> = PolynomialRing(GF(4))
S.<a> = R.quo(sage.rings.ideal.FieldIdeal(R))
S.is_finite()
Then I could iterate over $S$ and simply lift all the elements from $S$ back to $R$, i.e. s.lift(). The same thing however does not work for several polynomials:
R.<x,y> = PolynomialRing(GF(4))
S.<a,b> = R.quo(sage.rings.ideal.FieldIdeal(R))
S.is_finite()
yields the error
> AttributeError: 'super' object has no attribute 'is_finite'
As an alternative I could manually generate all multivariate polynomials with exponents less than the order of the field. However, this seems quite tedious and like a very "un-sage"/not algebraic way.philipp7Mon, 02 Mar 2020 15:27:09 +0100https://ask.sagemath.org/question/50136/Square roots in finite fieldshttps://ask.sagemath.org/question/47596/square-roots-in-finite-fields/ In a finite field, say
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
F = GF(p)
does the square_root function always return the root r s.t. sign(r) = +1, assuming that a root exists, where sign is the function that return -1 iff r > (p-1)/2NikolajMon, 26 Aug 2019 16:50:40 +0200https://ask.sagemath.org/question/47596/square root signhttps://ask.sagemath.org/question/47595/square-root-sign/ In a finite field, say
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
F = GF(p)
does the square_root function always return the root r s.t. sign(r) = +1, assuming that a root exists, where sign is the function that return -1 iff r > (p-1)/2NikolajMon, 26 Aug 2019 16:50:07 +0200https://ask.sagemath.org/question/47595/Symbolic computations in a finite fieldhttps://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/Hallo
I am interested in symbolic computations in a file field. Working in the field $GF(2^8)$ with $x$ as a generator and a variable $y$, also there is a function $f:GF(2^8)\rightarrow GF(2^8)$ of which the exact definition is not given. Can sage do the following:
$(x + y) ^ {2^8} \mapsto x + y$
$(x + y) ^ {2^6} \mapsto x ^ {2^6} + y ^ {2^6}$
$f(y) + f(y) \mapsto 0\cdot x$
If sage cannot do it does there exist another program which can?
_______________________________________________________________
Below is my question updated:
For the function I have a partial solution but I cannot mix it with an element of an finite field
<pre>
<code>
import sympy
f = sympy.Function('f')
y = var('y')
sympy.expand((f(y)+f(y)), modulus=2)
</code>
</pre>
When I want to add an element of a finite field
<pre>
<code>
import sympy
f = sympy.Function('f')
x = GF(2^8,'x').gen()
f(x)
f(x) + x
</code>
</pre>
the statement $f(x) +x$ give me an error that makes sense ... TypeError: unsupported operand parent(s) for '+': 'f' and 'Finite Field
in g of size 2^8'
To create a variable in a finite field I decided to use a Polynomial ring
<pre>
<code>
import sympy
f = sympy.Function('f')
R.< x > = PolynomialRing(GF(2))
f(x)
f(x) + x
</code>
</pre>
both $f(x)$ and $f(x) + x$ fails with a very long Trace message.
RegardsJohanMon, 22 Jul 2013 05:49:28 +0200https://ask.sagemath.org/question/10371/Roots of Polynomials over finite Fieldshttps://ask.sagemath.org/question/43734/roots-of-polynomials-over-finite-fields/Hi guys,
How can I define all polynomial as this form -> `a*x^2+b*y-1` over QQ where `a` and `b` are constants.
for examples polynomials as : `2*x^2+3*y-1` or `5*x^2+y-1` , ...
I know that I have to create a PolynomialRing, but I don't understand how exactly.
Thank you so much.ZacariasSatrusteguiSun, 23 Sep 2018 20:17:59 +0200https://ask.sagemath.org/question/43734/How to compute common zeros of system of polynomial equations with dimension 2?https://ask.sagemath.org/question/42591/how-to-compute-common-zeros-of-system-of-polynomial-equations-with-dimension-2/I have some ideal of homogenous polynomials defined over some finite field:
J is the ideal of interest. However I can't call J.variety() since it is not zero dimensional. The system of equations might contain 6 or 231 polynomials in four variables:
sage: [I.gens() for I in J.minimal_associated_primes()]
[[x1 + x2, x0 + x3], [x2 + x3, x0 + x1], [x1 + x3, x0 + x2]]
sage: J.dimension()
2
Any ideas?
On request. The program computes the invariant under the group $2_{+}^{1+2\cdot2}$ homogenous polynomials of given degree. To construct the polynomials and get a list of them call: homInvar(6):
F = ZZ;
a = matrix(F, [[0,0,0,-1],[0,0,1,0],[0,-1,0,0],[1,0,0,0]])
b = matrix(F, [[1,0,0,0],[0,1,0,0],[0,0,-1,0],[0,0,0,-1]])
c = matrix(F, [[0,1,0,0],[-1,0,0,0],[0,0,0,1],[0,0,-1,0]])
d = matrix(F, [[0,1,0,0],[1,0,0,0],[0,0,0,-1],[0,0,-1,0]])
def getPart(deg):
part = []
for k in range(deg+1):
for l in range(deg+1):
for m in range(deg+1):
for n in range(deg+1):
if k+l+m+n == deg:
part.append((k,l,n,m))
return part
def p(x,part):
x = x.list()
pol = 0
for p in [part]:
mon = 1
for i in range(len(p)):
k = p[i]
mon = mon * x[i]**k
pol = pol + mon
return pol
def getGroup():
G = []
for k in range(4):
for l in range(4):
for m in range(4):
for n in range(4):
g = a**k*b**l*c**m*d**n
if G.count(g)==0:
G.append(g)
return G
def reynolds(Gr,part):
reyn = 0
n = len(part)
X = list(var('x%d' % i) for i in range(n))
x = matrix([X]).transpose()
for g in Gr:
reyn += p(g*x,part=part)
#print reyn
return 1/len(Gr)* reyn
def homInvar(deg,Gr=getGroup(),getPart=getPart):
parts = getPart(deg)
inv = set([])
for part in parts:
r = reynolds(Gr,part)
#print r
if r != 0:
inv.add(r)
return invsagemathuserThu, 14 Jun 2018 12:49:21 +0200https://ask.sagemath.org/question/42591/kernel of a matrix defined over polynomial ringshttps://ask.sagemath.org/question/42453/kernel-of-a-matrix-defined-over-polynomial-rings/ I have a matrix defined as a function of variables in a polynomial ring defined over finite field as follows-
Gr.<xp,yp>=LaurentPolynomialRing(GF(2));
M=Matrix(Gr,[[xp-1,0],
[yp-1,0],
[0,(yp^(-1))-1],
[0,-(xp^(-1))+1]]);
I want to calculate the kernel of this matrix but the kernel function
M.kernel()
gives an error. What am I doing wrong?arpitMon, 28 May 2018 00:40:42 +0200https://ask.sagemath.org/question/42453/Correct way to construct a field with i adjoined?https://ask.sagemath.org/question/42420/correct-way-to-construct-a-field-with-i-adjoined/Hello,
I'm an undergrad maths student looking to understand how I successfully adjoin elements to a finite field in sagemath, to explore some of my university topics.
I can construct a base field, for example:
B = GF(2**3-1)
and I can construct an extension to this by adjoining I, which is equivalent to using the minimum polynomial x^2+1 like so:
reset('i') # make sure we haven't clobbered the imaginary constant
E = B[i]
This does what I want (I think), creating a field E that is an extension of B. We can even list the elements:
[e for e in enumerate(E)]
and this looks correct. However, things get messy when I try to use a larger field, for example:
C = GF(2**127-1)
F = C[i]
This gives the error:
> I already exists with incompatible valence
I haven't tried to redefine i at all, so far as I can tell, so, my questions are:
1. How do I correctly extend a given finite field ?
2. Following on from this, I tried the following:
A = GF(2**3-1)
B = A[i]
C = A.extension(x^2+1, 'i')
B==C
So it appears I can't successfully adjoin 'i' using a minimum irr poly either. Printing B and C give:
sage: B
Finite Field in I of size 7^2
sage: C
Finite Field in i of size 7^2
which would explain why they aren't equal... except i and I should be equal.
In short, I would like to construct the quotient field PRIME BASE FIELD[x]/x^2-1 and have the arbitrary x treated as complex values ("adjoining sqrt(-1)") but I'm unclear from sage's documentation on how to achieve this.
3. I see the notation
R.<x> = GF(blah)
quite a lot. Can someone please explain it? I can't find anything in the documentation that might help me understand what this is and why it is necessary.
You can assume I understand most of an undergraduate galois theory course and have a basic understanding of algebraic number theory - what I don't understand is how this maps into sage.zahllosThu, 24 May 2018 15:52:10 +0200https://ask.sagemath.org/question/42420/Square root of polynomial modulo another irreducible polynomialhttps://ask.sagemath.org/question/42042/square-root-of-polynomial-modulo-another-irreducible-polynomial/Hello,
If I'm not wrong, it is always possible to compute the square root of a polynomial $P$ modulo an irreducible polynomial $g$ when the base field is in $GF(2^m)$, i.e. find $Q \in GF(2^m)$ such that $Q^2 \equiv P \mod g$. Indeed, the operation $Q \rightarrow Q^2 \pmod g$ should be linear (because we are in $GF(2^m)$) so an idea would be to compute the matrix $T$ that perform this operation, and then invert it, but I'd like to find an embedded operation in sage. I tried the sagemath $P.sqrt()$ method, but the problem is that because it does not take into account the modulo, it fails most of the time when the polynomial has some terms with odd power of $X$.
Any idea?
Thanks!tobiasBoraMon, 16 Apr 2018 09:57:45 +0200https://ask.sagemath.org/question/42042/irreducible polynomial defining the finite fieldhttps://ask.sagemath.org/question/41473/irreducible-polynomial-defining-the-finite-field/X = GF(2).polynomial_ring().gen()
F = GF(2^8, name="a", modulus=X^8 + X^6 + X^5 + X + 1)
As example above, the polynomial X^8 + X^6 + X^5 + X + 1 is one of irreducible polynomial defining the finite field GF(2^8).
How can I get all the irreducible polynomial which can define the finite field GF(2^8)?omggggggSat, 10 Mar 2018 18:22:06 +0100https://ask.sagemath.org/question/41473/How to generate a cyclic matrixhttps://ask.sagemath.org/question/41000/how-to-generate-a-cyclic-matrix/ How to generate all 8×8 cyclic matrix $A$ with the first row $(a_0, a_1, \ldots, a_7)$,
the matrix $A\in GL(8, 2)$ and the first row $a_0 + a_1 + \ldots + a_7 \neq 0$
omggggggTue, 06 Feb 2018 19:22:26 +0100https://ask.sagemath.org/question/41000/Lagrange interpolation over a finite fieldhttps://ask.sagemath.org/question/39732/lagrange-interpolation-over-a-finite-field/Sorry if this is obvious I am not a mathematician and am only trying to do this to learn about Samir's Secret Sharing scheme which uses a finite field for security.
I've read the Sage doc here on univariate polynomial rings which works fine. but now I am curious as to how this would be done over a finite field instead in sage?
Is it simply a matter of every point being taken mod some prime? Or would this not work.GriphookWed, 22 Nov 2017 20:13:14 +0100https://ask.sagemath.org/question/39732/calculating the modulo of a "number" in a binary finite fieldhttps://ask.sagemath.org/question/38735/calculating-the-modulo-of-a-number-in-a-binary-finite-field/Polynomial equations in binary finite fields are often represented as numbers. eg. $x^2 + 1$ is basically the same thing as $1x^2 + 0x^1 + 1x^0$ and thus would be represented as $101_2$ or $5_{10}$.
In that spirit I'm trying to use a hexadecimal number to represent a polynomial equation. The polynomial equation is larger than the modulo I'm using ($x^{113} + x^9 + 1$) so I'm trying to get the result of the modulo operation.
Here's what I've tried:
BF.<a> = FiniteField(2^113);
X = Integer(0x61661990d3b1f7a608ad095a01d727380850d2592f5b9f88f66a20e8);
X_bf = BF._cache.fetch_int(X);
X_bf.mod(x^113 + x^9 + 1)
Unfortunately, this doesn't seem to work and instead gets me the following error messages:
TypeError Traceback (most recent call last)
<ipython-input-4-dba4addbde0d> in <module>()
2
3 X = Integer(Integer(0x61661990d3b1f7a608ad095a01d727380850d2592f5b9f88f66a20e8));
----> 4 X_bf = BF._cache.fetch_int(X);
5
6 X_bf.mod(x**Integer(113) + x**Integer(9) + Integer(1))
/home/sage/sage-8.0/src/sage/rings/finite_rings/element_ntl_gf2e.pyx in sage.rings.finite_rings.element_ntl_gf2e.Cache_ntl_gf2e.fetch_int (/home/sage/sage/src/build/cythonized/sage/rings/finite_rings/element_ntl_gf2e.cpp:7596)()
400 raise ValueError("Cannot coerce element %s to this field." % e)
401
--> 402 cpdef FiniteField_ntl_gf2eElement fetch_int(self, number):
403 """
404 Given an integer less than `p^n` with base `2`
/home/sage/sage-8.0/src/sage/rings/finite_rings/element_ntl_gf2e.pyx in sage.rings.finite_rings.element_ntl_gf2e.Cache_ntl_gf2e.fetch_int (/home/sage/sage/src/build/cythonized/sage/rings/finite_rings/element_ntl_gf2e.cpp:7212)()
431
432 if number < 0 or number >= self.order():
--> 433 raise TypeError("n must be between 0 and self.order()")
434
435 if isinstance(number, int) or isinstance(number, long):
TypeError: n must be between 0 and self.order()
I realize that what I'm doing isn't technically a finite field but idk how else I might get a "number" turned into a polynomial equation.
Any ideas?neubertMon, 04 Sep 2017 08:02:35 +0200https://ask.sagemath.org/question/38735/pre-reduction multiplication result in binary fieldhttps://ask.sagemath.org/question/38734/pre-reduction-multiplication-result-in-binary-field/The following will do multiplication in a finite field:
X = Integer(0x009D73616F35F4AB1407D73562C10F);
Y = Integer(0x00A52830277958EE84D1315ED31886);
F.<x> = GF(2)[];
p = x^113 + x^9 + 1;
BF = GF(2^113, 'x', modulus=p);
X_bf = BF._cache.fetch_int(X);
Y_bf = BF._cache.fetch_int(Y);
temp = Y * X; temp
The problem with this is that the result you get back has had the reduction step already ran. I'd like to see the multiplication result pre-reduction.
Any ideas?neubertMon, 04 Sep 2017 05:44:52 +0200https://ask.sagemath.org/question/38734/Several matrix multiplications over binary fieldshttps://ask.sagemath.org/question/38251/several-matrix-multiplications-over-binary-fields/Hi! I need to compute the product of several matrices with entries in a binary field. Since products do not depend on each other, computations can be easily distributed among the processors. However results of sequencial code and in processes are almost the same!
Here some code of a simple test that represents what I want to achieve:
from sage.all import *
import multiprocessing as mp
from multiprocessing.pool import ThreadPool, cpu_count
import time
def matrix_mult(A, B):
start = time.time()
A*B
return time.time() - start
def matrix_mult_proc(A, B, n):
avg = 0.0
for i in range(n):
start = time.time()
A*B
avg += (time.time() - start)
# print('time: {}'.format(time.time() - start))
print('Average per call proc {}: {}'.format(os.getpid(), avg / n))
@parallel
def matrix_mult_parallel(A, B):
start = time.time()
A*B
return time.time() - start
# print('time: {}'.format(time.time() - start))
iters = 40
n = 100
Fq = GF(2**16, 'X')
MS = MatrixSpace(Fq, n)
A = MS.random_element()
start = time.time()
tms = map(lambda i: matrix_mult(A, A), range(iters))
print('\n*** sequencial:\nAverage per call: {}\nTotal: {}'.format(sum(tms) / iters,time.time() - start))
nthreads = cpu_count()
pool = ThreadPool(nthreads)
start = time.time()
tms = pool.map(lambda i: matrix_mult(A, A), range(iters))
print('\n*** multithread {} threads:\nAverage per call: {}\nTotal: {}'.format(nthreads, sum(tms) / iters,time.time() - start))
nprocs = cpu_count()
procs = []
start = time.time()
print('\n*** multiproc {} procs:'.format(nprocs))
for i in range(nprocs):
p = mp.Process(target=matrix_mult_proc, args=(A, A, iters//nprocs))#, out_q))
procs.append(p)
p.start()
for p in procs:
p.join()
print('Total: {}'.format(time.time() - start))
args = [(A, A)]*iters
start = time.time()
tms = map(lambda e: e[1], list(matrix_mult_parallel(args)))
print('\n*** sage_parallel\nAverage per call: {}\nTotal {}'.format(sum(tms) / iters, time.time() - start))
Results are as follow:
For sequencial
Average time of a matrix multiplication: 0.279646992683
Total time for 40 multiplications: 11.1862668991
For Threadpool with 4 threads maximum
Average time of a matrix multiplication: 0.280531394482
Total time for 40 multiplications: 11.2248089314
For 4 processes in a 4 core computer (2 physical):
Average time of a matrix multiplication: 1.13726825714
Total time for 40 multiplications: 11.7641329765
With sage's @parallel decorator:
Average time of a matrix multiplication: 1.1256641984
Total time for 40 multiplications: 11.7641329765
I don't understand why multiplications seem to take a proportional amount of time to the number of processes. Same behavior on a 8 core machine.
Hope someone can explain. Thanks in advance.egonzalezFri, 14 Jul 2017 04:17:23 +0200https://ask.sagemath.org/question/38251/computing order of elliptic curves over binary fieldhttps://ask.sagemath.org/question/8919/computing-order-of-elliptic-curves-over-binary-field/Do you have any information on how to compute order of elliptic curves over binary field in SAGE mathematics software?
Example: I have the following domain parameters which are taken from
p = 0800000000000000000000000000000000000000C9
a = 07B6882CAAEFA84F9554FF8428BD88E246D2782AE2
b = 0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9
x = 0369979697AB43897789566789567F787A7876A654
y = 00435EDB42EFAFB2989D51FEFCE3C80988F41FF883
The problem I am facing is to to know the order of this elliptic curve? I ahve got on the net that it is possible to compute using this library sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari and it takes these parameters properly with out any error. But there is error while requesting the order of that parameter.
This was what I deed in sage:
FF = sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari;
order = 2**163;
c = 07B6882CAAEFA84F9554FF8428BD88E246D2782AE2;
b = 0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9
K.<x>= GF(2)[];
K.<k> = FF(order, 'a', modulus = x^163 + x^7 + x^6 + x^3 + 1)[];
K163_curve = EllipticCurve(K,[1,c,0,0,b]);K163_curve
twoforoneTue, 24 Apr 2012 11:15:06 +0200https://ask.sagemath.org/question/8919/Trace function over GF(q)https://ask.sagemath.org/question/8891/trace-function-over-gfq/Hi,
I understand the idea of defining functions over GF(q) which You explained me very precisely.
Now I have following problem:
I want to define the function:
`f(x,y)=Tr(x*g(y/x))`, where `Tr(x)=x+x^2+x^4` (`Tr:GF(8)-->GF(2)`) and
x*g(y/x)=[(y*[d^2*[(y/x)^3+1]+d^2*(1+d+d^2)*[(y/x)^2+(y/x)]])/((y/x)^4+d^2*(y/x)^2+1)]+(y/x)^(1/2).
Let (for example) d=3.
With convention that 1/0=0 (y/0=0), I want to see what values this function f receives. How can I do this in SAGE?
What I did (with Yours help):
def custom_divide(x,y):
if y==0:
return 0
return x/y
F.<a>=GF(8)
for a,b in F^2:
print "x: ",a,"y: ",b,"x/y: ",custom_divide(a,b)
F.<a>=GF(8)
for a,b in F^2:
print "x*y: ",a*b,"(x*y)^2: ",(a*b)^2,"(x*y)^(1/2): ",(a*b).nth_root(2)
I'm stopped here because I'm not sure how can I define such function f.
Any help/advices will be highly appreciated.
I could write more details if something is not clear.
Best regards,
ArcziArczi84Sun, 15 Apr 2012 17:11:14 +0200https://ask.sagemath.org/question/8891/inverse of a polynomial modulo another polynomialhttps://ask.sagemath.org/question/8756/inverse-of-a-polynomial-modulo-another-polynomial/Hi, I'm trying to implement the Baby Step Giant Step algorithm in the group of units of prime fields. I would like to generate the field provided one generator polynomial. But I need to calculate p^(-1) (where p is a polynomial), but can't find a function to do so. This is what I'm doing,
F.<a> = GF(2)[];
R.<b> = PolynomialRing(F)
S.<x> = R.quotient(b^4+b+1)
m = sqrt(S.modulus().degree());
gamma = S.modulus();
alpha = x^3+1;
now i need to calculate (alpha)^(-1) modulo gamma
Any help? Better ways to do the same thing?
Thanks!
inertialFrostTue, 28 Feb 2012 11:47:08 +0100https://ask.sagemath.org/question/8756/Unitary matrices over finite fieldshttps://ask.sagemath.org/question/9667/unitary-matrices-over-finite-fields/Hi everyone
I was delighted to see that the SAGE team had implemented the unitary groups GU(n,q) and SU(n,q), since they are such peculiar objects; however the implementation does not seem to include many matrix functions (eg det, trace, transpose etc.).
Let S be a (small) subset of GF(q^2). Let G=GU(n,q) and define a subset D_S of G (ie D_S is NOT a vector subspace or subgroup or anything) to be the matrices whose entries may only be chosen from this particular subset S. Let U, V in D_S. I need to check the matrix products (U^t)V for membership of D_S, where U^t denotes U.transpose() acted on by Frobenius in the usual way, and ideally I would like to store the set of pairs P = {(U,V) satisfying (U^t)V in D_S}, or even better to store some "generators" for P.
I have two questions:
(1) which matrix operations are available for elements of GU(n,q)?
(2) is there an easy way of specifying a sub-SET like D_S so that such a search may be performed? Needless to say once q and/or n gets any bigger than 3, holding any of these subsets naively in memory becomes prohibitively costly!
Many thanks for any help.
PS I can find generators for these groups using G.gens(); how please do I find relations between the gens?GaryMakSun, 30 Dec 2012 12:58:09 +0100https://ask.sagemath.org/question/9667/Generate a Matrix over a Finite Field with symbolic variableshttps://ask.sagemath.org/question/36148/generate-a-matrix-over-a-finite-field-with-symbolic-variables/ Hi everyone,
I am currently trying to generate a matrix over a finite field of 2 using symbolic variables a,b,c,and d instead of integers. The current problem I am having is that sage tries to convert these variables into integers and do not allow me to generate the matrix.
Inputting:
var('a, b, c, d')
m = matrix(GF(2), [[a,b], [e,f]])
gives me the error:
TypeError: unable to convert a to an integer
Please help, Thank you!!!benliuTue, 03 Jan 2017 16:47:45 +0100https://ask.sagemath.org/question/36148/residocity of elements in an extension of $\mathbb{F}_p$https://ask.sagemath.org/question/34817/residocity-of-elements-in-an-extension-of-mathbbf_p/Consider the following code :-
p=10010113
F=GF(p)
R=PolynomialRing(F,'x')
f=x^5 + 3212480*x^4 + 5943978*x^3 + 1041193*x^2 + 3212605*x + 4505026
F1.<a>=F.extension(f)
R1=PolynomialRing(F1,'x')
f1=derivative(f(x),x)
b=R1(f1(a))
b=F1(b)
Now since b $in $ F1 . Therefore `F1(b**p^5-1)` should output 1, but I am getting this output
sage: F1(b**(((p^5)-1)))
/usr/lib/sagemath/local/bin/sage-ipython:1: RuntimeWarning: invalid value encountered in power
#!/usr/bin/env python
9745575*a^4 + 8100949*a^3 + 6855548*a^2 + 351457*a + 548263
Which is absurd !vishbWed, 14 Sep 2016 16:06:29 +0200https://ask.sagemath.org/question/34817/Finding order of a polynomial over finite fieldhttps://ask.sagemath.org/question/34604/finding-order-of-a-polynomial-over-finite-field/**order** of a polynomial $f(x)$ in $\mathbb{F}_p [x]$ is defined as minimum $e$ such that $f(x) | x^e -1$ . Do we have an inbuilt function in sage to find the same ?vishbSat, 27 Aug 2016 08:06:49 +0200https://ask.sagemath.org/question/34604/What is the effect of declaring a polynomial `sparse'?https://ask.sagemath.org/question/34095/what-is-the-effect-of-declaring-a-polynomial-sparse/I do some work on polynomials over finite fields. Generated polynomials of larger degree are sparse in the sense that only a few coefficients are not zero. I tried to utilize this property by defining PR=PolynomialRing(GF(7),name='x',sparse=True). Then type(PR) is
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_field_with_category'>
what is not very informative. It is not clear which library is involved (FLINT, NTL, Sage's own implementation, or something else), and libraries FLINT, NTL seem not to support sparse polynomials (sparse in the sense of storing only the non-zero coefficients similar to sparse matrices).
So what does "sparse=True" mean? Is there a reduction of occupied memory? Anyway, time consumption for multiplication increases tremendously (I expected a major reduction).
Thanks in advance.
Function "make_pol" defined below generates for any target degree "deg" a polynomial over a finite field. Only about "deg^ex" coefficients are not zero where "ex" depends on the field's order and is in interval (1/2, 1), in particular "ex" is about 3/4 for field order 7. The reason for the sparsity is not yet understood. Multiplication of polynomials over GF(7) of degrees 100043 and 100361 (and 6144 coefficients each) generated this way takes 36 milliseconds for dense implementation but 29 seconds (without "milli"!) for sparse implementation (similarly for the function call, the function uses multiplications). If you are curious about the chosen degrees: these are Sophie Germain primes, they are of special interest since the generated polynomials are irreducible.
Platform info: 64 bit, 3.3GHz, Linux, Sage 7.1 (Release Date: 2016-03-20)
from sage.all import ZZ, GF, PolynomialRing
def make_pol(deg, char, sparse):
"""
Generate a sparse polynomial over a finite field.
INPUT:
"deg" target degree (natural number)
"ch" field characteristic (prime number)
"sparse" whether a sparse implementation to use (boolean)
OUTPUT:
Polynomial in 'x' of degree "deg" over field "GF(ch)".
Only about "deg^ex" (where "ex"<1) coefficients are not zero,
value of "ex" depends on "ch", e.g. "ex==3/4" for "ch==7".
"""
if not deg in ZZ or deg<0:
raise ValueError("First arg must be a non-negative integer.")
if not char in ZZ or not is_prime(ch):
raise ValueError("Second arg must be a prime number.")
R = PolynomialRing(GF(ch),'x',sparse=sparse)
i0 = 0
r0 = R(1)
s = R.gen()
if deg == 0:
return r0
i1 = 1
r1 = s+R(1)
if deg == 1:
return r1
i2 = 2
r2 = s*r1 - r0
if deg == 2:
return r2
k = 1
while i2 < deg:
if deg & k != 0:
i3 = 2*i2-i1
r3 = s*r2 - r1
i0 = i1
r0 = r1
i1 = i3
r1 = r3
else:
i1 = i2
r1 = r2
k = 2*k
s = s**2 - 2
i2 = 2*i1 - i0
r2 = s*r1 - r0
if deg == i2:
return r2
return r3
wjansenFri, 15 Jul 2016 17:20:06 +0200https://ask.sagemath.org/question/34095/Transform a list of coefficients to polynomial (in GF(2^8))https://ask.sagemath.org/question/29465/transform-a-list-of-coefficients-to-polynomial-in-gf28/ Hi there,
Currently i'm trying to convert a list of coefficients automatically to a polynom. I got a list of zeros and ones and want to transform this list to a polynom in GF(2^8). First I set up the GF(2^8) with the reduction polynom
P2.<x> = GF(2)[];
p = x^8 + x^4 + x^3 + x + 1;
GF256 = GF(2^8, 'x', modulus=p)
Next I get a list of coefficients:
coeff = [0, 1, 0, 1, 1, 1, 0, 1]
which should be the polynom:
x^6 + x^4 + x^3 + x^2 + 1
How do I get this transformation from list to polynom automatically? The native thing I think about is I set up a string and fill in the coeff. like this:
polyString = str(coeff[7])+'*x^7 + '+str(coeff[6])...
And then cast it in GF256
poly = GF256(polyString)
But I think they are smarter ways out there.. Any ideas ? :)
nablaheroWed, 16 Sep 2015 15:19:32 +0200https://ask.sagemath.org/question/29465/Checking Similarity of Matrices over Finite Fieldshttps://ask.sagemath.org/question/25352/checking-similarity-of-matrices-over-finite-fields/ Hi,
There is a command in SAGE which allows us to check the similarity of two matrices over Q (or sth); is_similar()
But,
when trying to check two matrices' similarity over Finite Fields it usually gives the error:
"unable to compute Jordan canonical form for matrix"
I would be appreciated if someone can help me to construct a practical way to check the similarity of two matrices with entries in Finite Fields.
Thanks in advance,algebraicallyclosedSun, 28 Dec 2014 00:55:18 +0100https://ask.sagemath.org/question/25352/Get coefficients of a polynomial in quotient ringhttps://ask.sagemath.org/question/24902/get-coefficients-of-a-polynomial-in-quotient-ring/Let say I have the following quotient ring:
F.<t> = PolynomialRing(GF(2), 'x').quotient(x^128 + x^7 + x^2 + x + 1);
Then I create a polynomial, for example t^128 which yields:
t^7 + t^2 + t + 1
Now how do I obtain the array of coefficients of this polynomial?
Or, similarly, how do I actually substitute 2 for t and evaluate this polynomial? The `subs` method doesn't work. (Probably the polynomial needs to be coerced to other ring with base field where 2 != 0).
NumberFourTue, 18 Nov 2014 13:04:35 +0100https://ask.sagemath.org/question/24902/Representing finite field elements in terms of subfield elementshttps://ask.sagemath.org/question/10904/representing-finite-field-elements-in-terms-of-subfield-elements/I am trying to do something along the lines of magma's Eltseq function between two finite fields of the same characteristic. I'm hoping that this will be easier now that the conway polynomial work has been included in sage.
Given an element of a finite field, I would like to be able to get that element as a polynomial in the generator of the finite field, but with coefficients in a non-prime subfield.
K.<w2> = FiniteField(2^2, conway=True, prefix="w")
L.<w4> = FiniteField(2^4, conway=True, prefix="w")
a = (w2+1)*w4 + 1 # a = w4^3 + w4^2 + w4 + 1
# Currently we can do this to get a polynomial with coefficients in the prime subfield:
a.polynomial().list() # returns [1, 1, 1, 1]
# I would like this same, but for any subfield:
a.polynomial(K).list() # would return [1, w2+1]
Does anything like this exist? I've been wracking my brain trying to work out how to do this in an efficient manner, but I can't come up with anything.
Any help in this, even just pointing me in the right direction, would be very much appreciated.hdsSat, 11 Jan 2014 15:36:15 +0100https://ask.sagemath.org/question/10904/how to run fraction elenment in Multivariate Polynomial Ring in over Finite Field ringhttps://ask.sagemath.org/question/10825/how-to-run-fraction-elenment-in-multivariate-polynomial-ring-in-over-finite-field-ring/how to run fraction elenment in Multivariate Polynomial Ring in over Finite Field ring
k.<a> = GF(27);k;k.list();(k.prime_subfield()).list()
k(a+1);k(3/4);k(3/56);k(3);k(5/8);k(5*a);k(a*8);k(5*a)/k(a*8);k(5*a)/k(a*8)==k(5/8)==k(50*a)/k(a*80);k(302*a)/k(a*301)==k(20/121)
frac=k.fraction_field();frac;k.is_integrally_closed();k.integral_closure().list()
F=Frac(k['x,y']);F;F(3*x/4);F(7*x/2-3);F(y)/F(y^2+3)
Fraction Field of Multivariate Polynomial Ring in x, y over Finite Field
in a of size 3^3
0
-x
Traceback (click to the left of this block for traceback)
...
NameError: name 'y' is not defined
k.divides(28*a, 3/4);k(28*a)/k(3/4)
True
Traceback (click to the left of this block for traceback)
...
ZeroDivisionError: division by zero in finite field.
cjshThu, 12 Dec 2013 03:34:24 +0100https://ask.sagemath.org/question/10825/