Re: nffactor() regression

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

On Thu, 13 Jun 2002, Igor Schein wrote:
> the command below enters an infinite loop in 2.2.4 on Alpha Linux.  It worked
> fine in 2.2.3
[...]

I and Xavier Roblot have been refurbishing my relative variant of van Hoeij's
method (to factor polynomials over number fields). We had not yet tested it
on 64 bit machines yet !

It broke in a trivial place. It is fixed (typo in nf_factor_bound, due to
3 == DEFAULTPREC on 64bit).

Btw, it would be a good idea to test heavily the polynomial factorization
routines, over Q (factor), and number fields (nffactor) [ factornf implements
Trager's method + van Hoeij over Z and is a desperate case unless the
degree of the field is very large compared to the degree of the polynomial.
It doesn't really require testing... ].

I have just (committed one hour ago) made important modifications to the
algorithm in the past week. Altough it works much better for my examples,
I might have broken something else. ( Van Hoeij's method is not exactly an
obvious thing to implement, and will require a lot of tuning. ) You can see
most relevant details at \g3.

I had tested Paul Zimmermann's factorization challenges

  http://www.loria.fr/~zimmerma/mupad/

before the release, so I'm probably tuned all right with respect to these. It
would be a good idea to check other types of polynomials.

Cheers,

    Karim.

P.S: The weak parts of the implementation are (quadratic) Hensel lifting for
large degrees and huge heights and, in nffactor, the computation of an
LLL-reduced basis for \wp^k in nffactor (when k is large, say 100 and more).

For the latter it may be the weak part of my algorithm, with nothing really
to blame about the implementation. I don't know yet.

As for Hensel lifting, for the tough examples (say degree 1000, 4000 digits)
it requires very efficient polynomial arithmetic, which we don't have. In
particular, all euclidean divisions should be preconditionned; also, we're
definitely in the FFT zone in that range, and we don't have one. Victor
Shoup's NTL (5.0c + gmp-3.1.1) is between 3 and 4 times faster than Pari for
this kind of inputs (already about twice faster for degree 500, 400 digits).

There are some impressive NTL timings at

  http://shoup.net/ntl/doc/tour-time.html

-- 
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas
--
PARI/GP Home Page: http://www.parigp-home.de/