Thanks -- interesting discussion! That would make a nice project for someone to implement in Sage.
John 2010/1/13 William Stein <wst...@gmail.com>: > On Tue, Jan 12, 2010 at 4:09 PM, Bill Hart <goodwillh...@googlemail.com> > wrote: >> The algorithm QUICK FACTOR in the von zur Gather - Kaltofen paper > > PDF attached to this email. > >> looks very easy to implement and only returns failure if you use a >> probabilistic univariate factoring algorithm. >> >> You could implement that in Sage probably with a very small amount of >> work. >> >> I don't suggest you'll get it down to 0.1s (after all, I don't think >> there is even fast univariate factoring over GF2 in Sage), but surely >> it will be better than forever (my guess would be less than a minute). >> >> There's much faster univariate factoring coming up in the next version >> of FLINT. But it won't be released for a while yet. >> >> Bill. >> >> On Jan 12, 3:22 pm, John Cremona <john.crem...@gmail.com> wrote: >>> 2010/1/12 YannLC <yannlaiglecha...@gmail.com>: >>> >>> >>> >>> > On Jan 12, 3:44 pm, John Cremona <john.crem...@gmail.com> wrote: >>> >> No, the van Hoeij / Belabas algorithms are for univariate polynomials, >>> >> over Q (and then over number fields). Pari does not have multivariate >>> >> polynomial factorization >>> >>> > It might not be implemented in Pari, but the algorithm has been >>> > further extended and works also for bivariate factorization over >>> > finite fields. >>> > See [20] here:http://www.ufr-mi.u-bordeaux.fr/~belabas/research/ >>> >>> That looks good. I'll email Karim and ask if he plans to have this in >>> pari any time soon. >>> >>> John >>> >>> >>> >>> > Yann >>> >>> > -- >>> > 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 >>> > athttp://groups.google.com/group/sage-devel >>> > URL:http://www.sagemath.org >> >> -- >> 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 >> >> > > > > -- > William Stein > Associate Professor of Mathematics > University of Washington > http://wstein.org > > -- > 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 > >
-- 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
