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.
