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.Sun, 18 Apr 2021 12:48:15 +0200Computing the factored multiplicative order of an extension field tries to solve an unnecessarily hard factoring problemhttps://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/There seems to be a unnecessary performance problem with constructing large extension fields:
sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001
sage: GF(p^2)
This hangs trying to factor the 891-bit integer $p^2 - 1$, which is longer than the longest solved RSA Challenge number. (As it happens, the hard part of this factorization is a 675-bit integer which is still impractical.)
It is not unreasonable that constructing the extension field requires knowing the factorization of the multiplicative order. (You can get around this by constructing it with a specific modulus, but then many operations, e.g. taking roots, require this factorization anyway.)
However, we know that $p^2 - 1$ splits as $(p-1)(p+1)$, and factoring those may be much more feasible:
sage: factor(p-1)
2^32 * 3^4 * 17 * 67 * 293 * 349 * 1997 * 19556633 * 44179799701097 * 1461985442088199434216480729118540833655826472878315075486478169293801719414121837587283877
sage: factor(p+1)
2 * 313 * 751 * 2003 * 2671 * 738231097 * 55047696457335561580180364861378466840614260303507426009866606293225963076275651294902969015038913167956483928299
(this takes less than a second on my desktop).
In general, computing the multiplicative order of an extension field should take advantage of the factorization of $p^k - 1$ as a polynomial. There might also be other cases where we know the factorization by construction, and should be able to provide it.dairaSun, 18 Apr 2021 12:48:15 +0200https://ask.sagemath.org/question/56710/Class to which an element belong in a quotient ringhttps://ask.sagemath.org/question/39013/class-to-which-an-element-belong-in-a-quotient-ring/Fellow Sages:
I wish to determine whether certain elements of the quotient ring $Q:=\mathbb{F}_{2}[x]/\langle (x^{5}-1)^2\rangle$ are units and, in the case they are indeed units, I would also like to compute their multiplicative orders. How can one go about doing this?
In case you consider that my previous questions is a wee bit too broad, I have a related question which is more specific: if $p(x) \in \mathbb{F}_{2}[x]$ and $k \in \mathbb{N}$, how does one even determine a representative of the class (in the quotient ring $Q$) to which $(p(x))^{k}$ belongs? The naïve approach does not seem to work here: in my viewpoint, the code
> F = GF(2)
>
> R.<x> = PolynomialRing(F)
>
> S.<a> = R.quo((x^5-1)^2)
>
> b=x^5-1
>
> b^2;
SHOULD output [0] because the image of $(x^{5}-1)^2$ under the natural projection $\mathbb{F}_{2}[x] \to Q$ is exactly equal to the zero element of the quotient ring $Q$, but it does not yield that (it outputs the polynomial $x^{10}+1$, duh!). Do you know how it is that I am supposed to modify it in order to get the class in $Q$ to which the power in question belongs?
Thanks in advance for your insightful replies!FordoSun, 01 Oct 2017 02:47:36 +0200https://ask.sagemath.org/question/39013/Taylor Series With Order (Big O)https://ask.sagemath.org/question/36665/taylor-series-with-order-big-o/ I'm trying to replicate some Mathematica code, and I know very little about Mathematica and Sage.
The Mathematica code creates a Taylor series for f(x) about (x0), with degree 5. I was able to replicate that.
x, x0, dt = var('x, x0, dt')
f = function('f')
t = f(x).taylor(x, x0, 5)
Next it does a substitution.
k1 = f(x0)*dt
s = x0 + k1/2
k2 = t.subs(x=s)
The problem is it that it then removes the higher order terms using the big O notation.
k2 = Expand[g[x] \[CapitalDelta]t /. x -> s] + O[\[CapitalDelta]t]^5
It looks like this is available for series and polynomial rings (no clue what those are) in SageMath, but I haven't figured out how to apply it to the Taylor series expansion.
Is there a way to truncate certain order terms off of an expression?
Is there a way to replicate the Taylor series expression I want with `.series()` or polynomial rings?
I tried importing `sage.rings.big_oh` and using `Order()` but neither seemed applicable to the expression I had. I also made half an attempt to recreate a Taylor series with `.series()` but didn't quite get what I was hoping for.
tq = 1/factorial(n)*f(x)*x^n
tq.series(n, 5)
Thanks for the help, both my math and SageMath skills are lacking.douggardSun, 19 Feb 2017 23:56:02 +0100https://ask.sagemath.org/question/36665/Pick a point at random on an elliptic curve with specific orderhttps://ask.sagemath.org/question/35921/pick-a-point-at-random-on-an-elliptic-curve-with-specific-order/Hi!
I use the function `random_point()` to pick a point at random on an elliptic curve, but I was wondering if there is a way to pick a point at random that has a specific order (or some useful geometric property that allows me to do that).
So far, brute forcing seems the only way to me (pick a point at random, check its order and iterate until it has the wanted order) but it's obviously very naive!
Thank you for your help!
Bahamut91Mon, 05 Dec 2016 17:16:21 +0100https://ask.sagemath.org/question/35921/Random point on elliptic curve with specific orderhttps://ask.sagemath.org/question/35920/random-point-on-elliptic-curve-with-specific-order/ Hi!
I use the function `random_point()` to pick a point at random on an elliptic curve, but I was wondering if there is a way to pick a point at random that has a specific order (or some useful geometric property that allows me to do that).
So far, brute forcing seems the only way to me (pick a point at random, check its order and iterate until it has the wanted order) but it's obviously very naive!
Thank you for your help!
Bahamut91Mon, 05 Dec 2016 17:14:53 +0100https://ask.sagemath.org/question/35920/Can I show ordered sets in order?https://ask.sagemath.org/question/34369/can-i-show-ordered-sets-in-order/ I'm using SageTex to generate random algebra tests, with an answer key at the end. To have my students show they understand roster notation for sets, I'm having them write the set of all two-digit multiples of n for some number n in {2, 3, 4, ... 9}. Asking the question isn't hard. But in generating the answer key, the set shows up in random order. I know it's still the same set, of course, but it's less intuitive to interpret. It seems like Sage is going out of it's way to randomize the set. Here's some minimal working code:
n = Set(range(2, 10)).random_element()
X = Set()
for i in range(10, 100):
if i % n == 0:
X = X.union(Set([i]))
show(n)
show(X)
This shows, for example:
8
{32, 64, 48, 40, 80, 96, 16, 24, 56, 72, 88}
Is there some way to have Sage show the elements of the set in order?mathochistMon, 08 Aug 2016 02:13:27 +0200https://ask.sagemath.org/question/34369/Why the function .cardinality() doesnt work with a permutation group ?https://ask.sagemath.org/question/27127/why-the-function-cardinality-doesnt-work-with-a-permutation-group/ I have acode that use to run very good, but I dont know why no longer the basic functions works for my permutation groups, i.e Abelian, cardinality, order. Only degree seems to workhbanosWed, 17 Jun 2015 08:05:34 +0200https://ask.sagemath.org/question/27127/Sorted list of symbolic eigenvalues (and corresponding eigenvectors)https://ask.sagemath.org/question/9599/sorted-list-of-symbolic-eigenvalues-and-corresponding-eigenvectors/Is there a way to obtain a sorted list of eigenvalues when they are computed symbolically (in SR). Particularly knowing that in specific points, they can switch order.
So far, what I have is (assuming $R^3$):
def sorted_eval(m, x, y, z, order=0):
_ev = m.eigenvalues()
_ev = numpy.array(ev.subs(x=x, y=y, z=z))
_ev.sort()
return _ev[order]
But then if I want to perform a contour plot:
x, y, z = var('x y z')
p = vector([x,y,z])
f = p * p
h = f.hessian()
contour(lambda x, y: sorted_eval(h, x, y, 0, 0), (x, -1.5, 1.5), (y, -1.5, 1.5))
It takes a long time
Thanks
D
DemMon, 03 Dec 2012 14:08:01 +0100https://ask.sagemath.org/question/9599/eigenvalues of a derivative vs derivative of eigenvalueshttps://ask.sagemath.org/question/9543/eigenvalues-of-a-derivative-vs-derivative-of-eigenvalues/Hi! I have this little problem. If anyone would be so kind to share his knowledge and shed some lite on it, I'd be very grateful. Big thanks in advance (and sorry for my english)!
I have a matrix M=M(x) depending on a variable x. I want sage to compute trace of a product of a derivative of M, M' and some function of it, f(M), at a fixed value of x=x_0; that is:
(tr[M'*f(M)])|_(x=x_0).
It just so happens that tr[M'*f(M)] = sum( ev_i' *f(ev_i) ), where {ev_i(x)} are eigenvalues of M. Lucky me. Diagonalisation of M commutes with differentiating or taking the function of it, one could say.
But my M and its derivative are somewhat complicated, yet simplify greatly after substituting x=x_0. So I would very much prefer first to compute M', substitute x_0 M0:=M|_(x=x_0) and M'0:=M'|_(x=x_0), and only after that ask sage for eigenvalues:
ev1=M0.eigenvalues()
ev2=M'0.eigenvalues()
So here's the question: do i have any reason for hoping that:
(tr[M'*f(M)])|_(x=x_0) = sum( ev2[i] *f(ev1[i]) for i in range(dim of M) )?
(That is, wether the order of eigenvalues changes if I exchange diagonalisation with differentiation?)ozikSat, 17 Nov 2012 19:18:33 +0100https://ask.sagemath.org/question/9543/Order of a differential equation?https://ask.sagemath.org/question/9113/order-of-a-differential-equation/Does it exists a method or a function that returns the the order of a (O-P)DE?Lucas_MalorSun, 15 Jul 2012 13:48:41 +0200https://ask.sagemath.org/question/9113/