> Is there any chance you could write an email explaining the basic > ideas behind your new factorization implementation? I'm just curious > what goes into it. Even something along the lines of this page would > be nice: > > http://magma.maths.usyd.edu.au/magma/htmlhelp/text315.htm > > -- William >
It's not very different from what other systems do. First of course square free factorization, then try a few (2) random values for all indeterminates except the first one, for a fast check of irreducibility. If not, lift the equality in one variable P(x,0,...0)=product P_i(x,0,...,0) more precisely, one must take care of the leading coefficient, hence lift P*lcoeff(P)^(#nfactors-1)=product P_i where in P_i the leading coefficient is replaced by lcoeff(P). In order to avoid densification (if lcoeff(P) has many coefficients), I make a bivariate factorization, this way instead of using lcoeff(P) for every P_i, I'm using a divisor of lcoeff(P). It's a little different from what is describe in the thesis of Bernardin (I don't make polynomial rational reconstructions for example). There is also a try to do sparse factorization before. If Hensel lift does not work (for example P(x,0...0) loose degree or has non square-free factors), I'm using "heuristic factorization", i.e. evaluate P at x>=2 linfnorm(P)+2, factor this polynomial, reconstruct factors (using x as basis and symmetric remainder) and check division, if remainder is 0 an irreducible factor has been found, otherwise try with a larger value of x. The corresponding code slices are in ezgcd.cc try_sparse_factor and try_hensel_lift_factor, and do_factor in gausspol.cc. -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
