Re: polredabs(,16)

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

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/