Re: polredabs(,16)

[Bill Allombert <allomber@math.u-bordeaux.fr>]

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.