Karim BELABAS on Tue, 18 Jun 2002 12:36:12 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: nffactor() regression |
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/