Re: polredabs(,16)

[Bill Allombert <allomber@math.u-bordeaux.fr>]

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.