Bill Allombert on Thu, 12 Sep 2002 17:24:24 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polredabs(,16) |
On Thu, Sep 12, 2002 at 03:17:26PM +0200, Karim BELABAS wrote: > 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). I have a simple algorithm for that. In fact I have even add the function FpX_gcd_check just for this purpose. The idea is to compute D=Disc(T)=Res(T,T') and try FpX_gcd_check(T, T', D). This must return a factor of D. If if is not one, we restart with the divisors: FpX_gcd_check(T, T', d), etc... This should be almost as good as polredabs(,,16). Bill.