Re: nffactor vs factornf

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* 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.
--
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]
`