Mark uses LLL to solve the knapsack problem that arises from solving how the local factors should be bundled together to reconstruct the global factors. It's only used to tame the combinatorial explosion that you get if there are many local factors, but only very few global ones. This is completely analogous in the multivariate situation, where your specializations give local factorizations. (i.e., take a square-free multivariate polynomial f(x,y), find a y0 such that f(x,y0) is also square-free, determine the factorization of f(x,y0), lift it to a power-series factorization of f(x,y0+z), use LLL to see how these factors pack together to give a polynomial factorization of f(x,y).
I can image that for polynomials, you can do something faster. However, if the combinatorial explosion is a problem there as well, Mark van Hoeij's trick should still apply. On Feb 18, 10:21 am, "William Stein" <[EMAIL PROTECTED]> wrote: > On Feb 18, 2008 10:08 AM, Roman Pearce <[EMAIL PROTECTED]> wrote: > > > > > On Feb 18, 6:21 am, Bill Hart <[EMAIL PROTECTED]> wrote: > > > Laurent Bernardin and Michael B. Monagan. > > > Efficient Multivariate Factorization Over Finite Fields. > > > If Sage has or can get fast LLL you should implement the new algorithm > > of Mark van Hoeij. > > Sage does have a very fast LLL implementation (fpLLL by Damien Stehle). > However, I don't know of any new (or old) algorithm by Mark van Hoeij > that addresses the problem of "Efficient Multivariate Factorization Over > Finite Fields" using LLL. Could you please clarify. > > I am aware of Mark's algorithms for univariate polynomial factorization > over global fields using LLL. > > -- William --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
