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.Mon, 25 Apr 2022 12:46:26 +0200factoring out a term - not only a variable - in a symbolic expressionhttps://ask.sagemath.org/question/62150/factoring-out-a-term-not-only-a-variable-in-a-symbolic-expression/I know that I can use collect to "factor out" a variable or arrange a symbolic expressions in powers of that variable.
But if there's a term, e.g. x+1, as common factor, I don't know how to factor it out. collect doesn't work for this, e.g.:
sage: var('c0 c1 c2 x0 x1 x')
sage: (c0 * (x+1) + c1*(x+1) + c2*c1*x - c0*c1*(x+1)).collect(x+1)
output: -c0*c1*(x + 1) + c1*c2*x + c0*(x + 1) + c1*(x + 1)
What I would like to have here is:
(-c0*c1 + c0 + c1)*(x + 1) + c1*c2*xAlbert_ZweisteinMon, 25 Apr 2022 12:46:26 +0200https://ask.sagemath.org/question/62150/Program stop at i=95https://ask.sagemath.org/question/61855/program-stop-at-i95/When I run the below code, the computer stopped at i=95:
for i in range(1,200):
n=round(pi*10^i);
p=factor(n)
print("i=",i,", n=",n,", p=",p)
Not sure why it happens or if that really is very slow case to process...
This case if I used Wolfram Alpha it gives as:
factor (round(pi*10^95))
2^2×739×106278506549045779379656406741525807990431982387520494620261995680237361511712077084845562427
(2 distinct prime factors, 1 distinct composite factor)jarkkyWed, 06 Apr 2022 10:42:25 +0200https://ask.sagemath.org/question/61855/Computing 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/another factoring polynomials questionhttps://ask.sagemath.org/question/49709/another-factoring-polynomials-question/I have the following expression:
f = u^2*v*x + 3*u*v^2*x + 2*v^3*x + u^2*x^2 + 5*u*v*x^2 + 5*v^2*x^2 + 2*u*x^3 + 4*v*x^3 + x^4 + 2*u^2*v*y + 6*u*v^2*y + 4*v^3*y + 2*u^2*x*y + 12*u*v*x*y + 12*v^2*x*y + 6*u*x^2*y + 12*v*x^2*y + 4*x^3*y + u^2*y^2 + 6*u*v*y^2 + 6*v^2*y^2 + 6*u*x*y^2 + 12*v*x*y^2 + 5*x^2*y^2 + 2*u*y^3 + 4*v*y^3 + 2*x*y^3 + u^2*v*z + 3*u*v^2*z + 2*v^3*z + u^2*x*z + 6*u*v*x*z + 6*v^2*x*z + 3*u*x^2*z + 6*v*x^2*z + 2*x^3*z + u^2*y*z + 6*u*v*y*z + 6*v^2*y*z + 6*u*x*y*z + 12*v*x*y*z + 5*x^2*y*z + 3*u*y^2*z + 6*v*y^2*z + 3*x*y^2*z + u*v*z^2 + v^2*z^2 + u*x*z^2 + 2*v*x*z^2 + x^2*z^2 + u*y*z^2 + 2*v*y*z^2 + x*y*z^2
and I would like to simplify it by gathering and factoring partial sums
u, u+v,...,u+v+x+y+z
v, v+x,...,v+x+y+z
x, x+y,x+y+z,
y,y+z
z
(I have reason to expect that the expression will look quite a bit nicer if I do this, introducing notation for the sums of course, like h_{ij} = the sum of variables i up to j)
My first lame try at this was to ask sage to rational_simplify() quotients f/(u+v+x+y+z),...,f/(u+v), and so on, hoping to see more than just one big fraction. It didn't work.
Any insights/suggestions/corrections would be much appreciated!
Thanks,
anneWed, 29 Jan 2020 18:27:50 +0100https://ask.sagemath.org/question/49709/qsieve errorhttps://ask.sagemath.org/question/48549/qsieve-error/ I'm trying to run the qsieve function in sage (version 8.9) and I'm getting a file or directory error.
For example, when I try the code
n = next_prime(10^20)*next_prime(10^21)
q,t = qsieve(n,time = True)
I get the error,
OSError: [Errno 2] No such file or directory.
I tried looking up if there was an additional library or package I needed to download to make the qsieve function work, but I couldn't find anything. Any advice or insight would be appreciated.
JRHalesTue, 29 Oct 2019 15:44:32 +0100https://ask.sagemath.org/question/48549/Factoring vs Prime identificationhttps://ask.sagemath.org/question/48207/factoring-vs-prime-identification/Hey folks,
I generated two random primes, using `random_prime(2^256)`
Which gave me:
26743933906960470604491354271488742656120020729367854162490438790852133849203
and
58989902932261902911492570960628926646065206682060380716310751283003413744077
Multiplying them to get a semiprime I get:
1577622065198425994274982187337138762115683359284991921617675178559462773099557341124448864625540436189444788629927033127980383957266963291159527952420631
So maybe this is my miscomprehension, but when I try to run:
factor(on the semiprime) -- it takes a long time, never completing.
When I run
isPrime(on the semiprime) -- it instantly returns false.
If indeed sage generates proper primes (non pseudoprimes) how can isPrime be so efficient. Does verifying that a number ISNT prime, not require identifying a factor? If so, why does factorisation take so long?
Thanks
john_alanSun, 06 Oct 2019 19:16:44 +0200https://ask.sagemath.org/question/48207/Find factors of large integers without fully factoringhttps://ask.sagemath.org/question/44646/find-factors-of-large-integers-without-fully-factoring/I have to find the smallest factor of a big number with SAGE. The problem with the factor command is that it displays the results only when the number is fully factored and so for a big number it could take an eternity to have the result. Has somebody a good program for finding factors of a big number without waiting for a full factorization?polistiroloWed, 12 Dec 2018 09:32:17 +0100https://ask.sagemath.org/question/44646/how does sage factor a Mersenne number?https://ask.sagemath.org/question/34733/how-does-sage-factor-a-mersenne-number/ E.g. 2^67-1. Does it simply have/use a lookup-table for Mersennes?randyhMon, 05 Sep 2016 21:25:32 +0200https://ask.sagemath.org/question/34733/Large Integer Factorizationhttps://ask.sagemath.org/question/34125/large-integer-factorization/I am trying to factor a 520-bit integer in Sage. At some point, I get:
**Warning: MPQS: number too big to be factored with MPQS, giving up.**
But it seems to still be running. Is it continuing the factorization?VovaMon, 18 Jul 2016 14:47:59 +0200https://ask.sagemath.org/question/34125/Applying Memoized to Recursive Functionhttps://ask.sagemath.org/question/30384/applying-memoized-to-recursive-function/Does anyone know how to apply memoized function to a recursive function? specifically the def f(xn) function in the following function?
I am trying to improve the following code to be able to factor a numbers. It seems to work well for values like 7331116 and 7331118 but 7331117 results in a recursion depth error and I can't figure out how to improve the code. Someone suggested to me to memoize the def f(xn) function but all can find online is that you add @CachedFunction right before the function is declared but it doesn't seem to help.
def pollard_Rho(n):
def f(xn):
# This calculates f(x) = x^2+1 based on x0=2.
return (1 + f(xn-1)**2)%n if xn else 2
i=0 # Counting variable
x=f(i) # calculating x of the pollard rho method.
y=f(f(i)) # calculating y of the pollard rho method.
d=gcd(abs(x-y),n) # calculating gcd to construct loop.
while d==1: # A loop looking for a non 1 interesting gcd.
i = i + 1 # counting iterations
d=gcd(abs(x-y),n)
print d # Printing d=gcd for debugging purposes.
root1=d # Yes! found a factor, now we can find the other one.
root2=n/d # Hey! Here is the other factor!
print i + 1 # debugging print out.
return (root1,root2) # Kick those factors out into the world.
print pollard_Rho(7331118)
Fixed indentation.KristofferHSun, 01 Nov 2015 04:19:28 +0100https://ask.sagemath.org/question/30384/Factoring expression involving exponentialshttps://ask.sagemath.org/question/29823/factoring-expression-involving-exponentials/ I've got a complicated expression, which looks like:
e(4ik+3iω+ip)−e(4ik+2iω+2ip)−e(4ik+2iω)+e(4ik+iω+ip)+2e(2ik+4iω+ip)−e(2ik+3iω+2ip)−e(2ik+3iω) + ...
How would you do to factor the exponentials with the same power of k, i.e. e(4ik)*(...) + e(2ik)*(...) and so on?
mforetsThu, 08 Oct 2015 10:34:33 +0200https://ask.sagemath.org/question/29823/How to factor polynomials in var('x') over the semi-ring of polynomials with non-negative integer coefficients ?https://ask.sagemath.org/question/10689/how-to-factor-polynomials-in-varx-over-the-semi-ring-of-polynomials-with-non-negative-integer-coefficients/Is there an easy way in sage to determine the factorization of a polynomial in the variable x ( having non-negative integer coefficients), over the semi-ring of polynomials in the variable x with non-negative integer coefficients. EdinahSun, 03 Nov 2013 06:06:34 +0100https://ask.sagemath.org/question/10689/Powers of irreducible polynomialshttps://ask.sagemath.org/question/10296/powers-of-irreducible-polynomials/I'm working on a WeBWorK project to demonstrate the relatively new WeBWorK-Sage connectivity. We'd like to demonstrate some math problems that one could program in WeBWorK using Sage more cleanly than without Sage.
To that end I'm trying the following: WeBWorK would display a randomly generated polynomial in Z[x]. Let's say it could be degree 2, 3, or 4 with integer coefficients from [-10,10]. A student has to factor it completely.
I'm able to send the student's answer to Sage as a string, properly formatted for Sage. It might be '(x^2+1)*(2*x+1)' or '2*(x^2+3*x+2)*(x+2)^2'. But how can I evaluate whether or not the answer is fully factored? (For the moment, I'm not concerned about factoring out integers.)
So far, I have done this, where poly is the string passed to Sage:
<pre>
<code>
factored = True
if (poly).operator()!=operator.mul:
if (poly).polynomial(base_ring=QQ).is_irreducible():
factored = True
else:
factored = False
else:
factors = (poly).operands()
for factor in factors:
factored = factored and factor.polynomial(base_ring=QQ).is_irreducible()
print factored
</code>
</pre>
And factored is True if all of the factors in poly were irreducible, and False otherwise. This is not what I want since I want something like '(x+1)^2*(x+2)' to count as factored. Is there a quick test for whether or not a polynomial is a power of an irreducible? Or a constant multiple of such a thing?
alex.jordanSat, 29 Jun 2013 22:20:00 +0200https://ask.sagemath.org/question/10296/Polynomial arithmetic modulo prime powershttps://ask.sagemath.org/question/9166/polynomial-arithmetic-modulo-prime-powers/I'm trying to do some operations with polynomials over $Z/p^nZ$ and I'm stuck on some basic things:
1) Is it possible in SAGE to long divide two polynomials in $Z/p^nZ[x]$?
2) Is it possible in SAGE to factor a polynomial in $Z/p^nZ[x]$?
Am I missing something about the basic functionality of (1)? Is this really something that I need to program myself??
Robert PollackFri, 20 Jul 2012 14:37:12 +0200https://ask.sagemath.org/question/9166/Polynomial: distribute to greatest common factorhttps://ask.sagemath.org/question/9116/polynomial-distribute-to-greatest-common-factor/Hello, assuming I have a polinomial like this:
sage: var('x, y')
(x, y)
sage: y = 2*x^2 + x^3 + 10*x^4
is there a way to get it simplified applying the distributive property on the greatest common factor?
In this case, the output should be this:
y = x^2 * ( 2 + x + 10*x^2 )
Thank you!etuarduSun, 01 Jul 2012 13:29:49 +0200https://ask.sagemath.org/question/9116/Factoring polynomials over IntegerModRingshttps://ask.sagemath.org/question/8209/factoring-polynomials-over-integermodrings/I'd like to factor efficiently polynomials over rings (more particularly the rings of the form IntegerModRing(n), other rings don't interest me right now). I've noticed that you can factor a polynomial differently when considering FIELDS, so that something like
factor(x^2-2, QQ[])
factor(x^2-2, RR[])
will output the different expected results. But what about
x = var('x')
factor(x^5-x, IntegerModRing(25)['x'])?
What is actually outputted right now is
(x-1)*(x+1)*(x^2+1)*x
but the true factorization is
x*(x-1)*(x+1)*(x-7)*(x+7)
(I computed it by hand, Sage couldn't do it.) Going for small numbers like 25 is easy but when I go for large numbers I get nasty codes if I try to compute that myself. Isn't there anyway to make the factor command factor those polynomials or another way to do it? Any suggestion is welcome.
I am new to Sage and I am beginning to love its features since I begin to study number theory and Sage has plenty of options for that purpose, but I must admit they are quite hard to understand since I am also new to Python, PARI, Magma... (not to programming though!) explanations in detail would be deeply appreciated.Patrick Da SilvaSun, 03 Jul 2011 23:17:48 +0200https://ask.sagemath.org/question/8209/Is there an example of how i could write a polynomial as a product of linear factorshttps://ask.sagemath.org/question/7495/is-there-an-example-of-how-i-could-write-a-polynomial-as-a-product-of-linear-factors/Is there an example of how i could write a polynomial as a product of linear factors. newbie43Mon, 11 Oct 2010 11:50:32 +0200https://ask.sagemath.org/question/7495/