Karim BELABAS on Thu, 12 Sep 2002 15:17:26 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polredabs(,16) |
On Wed, 11 Sep 2002, Igor Schein wrote: > On Wed, Sep 11, 2002 at 04:39:28AM +0200, Karim BELABAS wrote: > > > I have modified the recovery code to enforce this (thereby discovering new > > factors, and reducing the number of failures). Does any of your examples > > break it ? > > There're actually a lot of degree-3 polynomials that don't get reduced > with flag=16. Here's one of the smaller ones > > x^3 - 5*x - 86089842541292486305497862178148061265660715093760132420 This is expected: using flag = 16, we may reduce a suborder of the maximal order. And it will actually occur whenever two relatively large (> primelimit) primes divide the discriminant, one of them to an odd power [ hence also dividing the field discriminant ]. flag = 16 is mostly useful when only "small" primes are ramified [ otherwise, it would be the default ! ] ? factor(poldisc(x^3 - 5*x - 86089842541292486305497862178148061265660715093760132420)); [...] [1000183 1] <---- this one is responsible [480860048849029 2] [781678926150510511345069276448469059 2] What can still be done is use a less naïve approach to "factor out small primes" (currently trial division only), e.g use (trial division + rho) [ ECM is probably too much already ], spending much less time rho than in the default factorint(). Say, number of rounds increases linearly with the discriminant size [ factorint() has a cubic increase once input gets large ]. In fact, this should be faster than pure trial division up to 'primelimit'. The best solution is probably to add a flag to factorint() for We need a good routine for "partial factorization of discriminants". Many functions need this (and currently do trial division only). Currently factorint() is not suited to the task since there's no way to override pollardbrent()'s tuning parameters [ which are geared towards complete factorization, _not_ "quick check just in case" ]. And modifying pollardbrent() is not enough, we still need (a large part of) the ifac_crack() machinery. Of course you still have the possibility to launch a full scale factorization in a different process and help out polredabs(,16) with the private primetable [ addprimes() ] if you're not happy with the results. Karim. -- 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/