ASKSAGE: Sage Q&A Forum - Latest question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 29 Jan 2020 11:27:50 -0600another 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 11:27:50 -0600https://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 09:44:32 -0500https://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 12:16:44 -0500https://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 02:32:17 -0600https://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 14:25:32 -0500https://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 07:47:59 -0500https://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.KristofferHSat, 31 Oct 2015 22:19:28 -0500https://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 03:34:33 -0500https://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 00:06:34 -0500https://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 15:20:00 -0500https://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 07:37:12 -0500https://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 06:29:49 -0500https://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 16:17:48 -0500https://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 04:50:32 -0500https://ask.sagemath.org/question/7495/