Re: nffactor() regression

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

On Mon, 17 Jun 2002, Igor Schein wrote:
> Here's another infinite loop:
>
> nffactor(nfinit(polcyclo(5,y)),x^48+12*x^46+948*x^44+7200*x^42+152361*x^40+815832*x^38+9475380*x^36+44654004*x^34+299137536*x^32+1335241260*x^30+5029216452*x^28+15282825984*x^26+37737671337*x^24+79579803672*x^22+143658877428*x^20+222699104460*x^18+303698198961*x^16+348787956312*x^14+312863646960*x^12+212893847424*x^10+111407984496*x^8+43762394880*x^6+11836253952*x^4+1904684544*x^2+136048896);

Generators for Van Hoeij's lattice contained 0 elements, I removed them.

It's an annoying problem: we LLL-reduce some lattice and project it to a
subspace, possibly decreasing its rank. IF we take the (HNF or LLL) image,
then we get correct rank but shatter the nice reduction properties (wrt to
our actual factorization problem). If not, we risk running into infinite
loops when the rank gets very small.

For the time being, factor() takes the HNF, and nffactor does not [ it only
checks whether a generator is 0 ]. I think nffactor is right ... provided you
can't find further infinite loops.

Possibly it will become necessary to abort the computation when the rank is
small enough, and finish with exhaustive enumeration of small vectors. I'd
like to avoid that.

    Karim.

P.S: van Hoeij's method is probabilistic in any case, it _may_ run into
infinite loops, if LLL fails to find the right small vectors. I strongly
doubt somehow will actually run into this once the implantation stabilizes,
though.
-- 
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/