Bill Allombert on Thu, 12 Sep 2002 19:07:24 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polredabs(,16) |
On Thu, Sep 12, 2002 at 06:47:27PM +0200, Karim BELABAS wrote: > On Thu, 12 Sep 2002, Bill Allombert wrote: > > > We need a good routine for "partial factorization of discriminants". > > > Many functions need this (and currently do trial division only). > > > > I have a simple algorithm for that. > > In fact I have even add the function FpX_gcd_check > > just for this purpose. > > The idea is to compute D=Disc(T)=Res(T,T') and > > try FpX_gcd_check(T, T', D). > > This must return a factor of D. If if is not one, we restart > > with the divisors: FpX_gcd_check(T, T', d), > > etc... > > This should be almost as good as polredabs(,,16). > > ... as a replacement for NFS :-)? > > Just tried it with install(). If does not fare well with Igor's example: > > x^3 - 5*x - 86089842541292486305497862178148061265660715093760132420 > > The only factor it finds is '10' [ once you remove the factor 100 from the > discriminant, you don't get anything new ] polredabs(,,16) is not better on this example, if we except trial division. FpX_gcd_check is much faster than a full nfbasis. This is useful with e.g. galoisinit. Igor, do you have example when this approach give less factors than polredabs(,,16) ? Cheers, Bill.