I think that there are carefully constructed polynomials of modest degree that will be surprisingly expensive to factor. For example, a polynomial that factors in all the finite fields that are attempted, but are irreducible over Z[x].
Randomly generated polynomials, as Nils says, are almost always irreducible. Products of two such polynomials will probably have exactly 2 factors in finite fields. Maxima concludes that P and Q are each irreducible in 0.015 and 0.90 sec resp. I set it to factor the product of P and Q, but I don't expect it to return before I finish this note. I don't know what are the current combination of algorithms and heuristics for factoring in Maxima. RJF On Thursday, November 3, 2016 at 12:37:58 PM UTC-7, Nils Bruin wrote: > > On Thursday, November 3, 2016 at 1:37:25 PM UTC-4, Dima Pasechnik wrote: >> >> >> >> On Thursday, November 3, 2016 at 1:06:05 PM UTC, Bill Hart wrote: >>> >>> >>> >>> On Friday, 28 October 2016 18:44:09 UTC+2, Dima Pasechnik wrote: >>>> >>>> 5 variables and degree 100 is really, really huge. Especially over QQ, >>>> the coefficients of >>>> polynomials will just totally blow. >>>> In fact, 5 variables and degree 10 might still be quite hard, in >>>> particular over QQ or other char. 0 fields. >>>> >>> >>> I disagree with all of the above, especially when the polynomials are >>> randomly generated. >>> >> >> Huh? Algebraic geometers are mostly not interested in random data. >> With probability 1, your random data will define something irreducible. >> While if your data is reducible, you might need to build algebraic >> extensions >> of high degree to factor. I don't see how you can handle extensions of >> degrees that might pop >> out of the data of this format... >> > > It should be easy for exactly the same reason why factoring over ZZ[x] is > fast: you reduce to factoring over GF(p)[x] and if you end up with a > square-free factorization, you lift p-adically. There's a (theoretical?) > issue of factor combination that is solved (theoretically as well as > practically) by LLL > > This works for multivariate factorization just as well: you specialize > variables and lift (repeatedly); you don't eliminate variables. No need to > build algebraic extensions. There are still details you need to check for > and you need to show you have a reasonable chance of not making unfortunate > choices, but polynomial factorization in general show be pretty efficient. > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
