Re: nffactor vs factornf

[Luis Felipe Tabera Alonso <taberalf@unican.es>]

On Friday July 16 2010, Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> 
wrote:
> * Luis Felipe Tabera Alonso [2010-07-15 21:25]:
> > According to the documentation, factornf uses Trager's trick to perform a
> > factorization over the rationals and nffactor uses Van Hoeij's method,
> > which is preferable in many cases, but it needs a nf structure.
> > 
> > I have some complicated number fields where I would like to factor
> > polynomials. If I already have the nf structure, I can use nffactor
> > without problems. But for these fields nf is very expensive, so factornf
> > is faster (I will not factor so many polynomials to do the effort).
> > 
> > But, as I understand Van Hoeij method, one does not need the nf
> > structure, it may increase performance though. I am correct? Is there a
> > way to use Van Hoeij's method without computing nf of the number field?
> 
> In the 'testing' branch, nffactor can live with a polynomial, instead of
> an nf structure, and compute internally the parts of the (missing) nf
> struct that it really needs :
> 
> \\ trivial example
> (00:08) gp > nf=nfinit(y^20-2); nffactor(nf,x^10-2);
> time = 156 ms.
> (00:08) gp > nffactor(y^20-2, x^10-2); \\ about as fast
> time = 156 ms.
> 
> \\ non-trivial example
> (00:08) gp > p= x^20 - 64857820*x^19 - 3862862*x^18 - 150*x^16 - 30*x^14 -
> 822*x^13 - 98578*x^11 + 8*x^9 + 43582*x^8 + 45*x^7 - 3033*x^6 -
> 1958664*x^4 + 493666*x^3 - 44*x + 1 (00:08) gp > nffactor(subst(p,x,y),p);
> time = 51,047 ms.
> (00:09) gp > nf=nfinit(subst(p,x,y)); nffactor(nf, p);
> time = 25,569 ms.
> 
> N.B: nfinit(p) was very lucky in this case : it tries to factor a
> general 200-digits integer, and succeeds "quickly" (because the latter is
> almost prime...)
> 
> 
> 
> What version are you using ?
> 
> Cheers,
> 
>     K.B.

Thanks for the fast answer!

I am using the testing branch 2.4.2.alpha, I will try this, looks very good. I 
can live with a performance penalty of not having the full nfinit since the 
beginning.

Luis


> --
> Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
> Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
> 351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
> F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
> `