Bill Allombert on Mon, 17 Mar 2003 23:47:14 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: QX_caract


On Sat, Mar 15, 2003 at 03:29:46PM +0100, Karim BELABAS wrote:
> On Wed, 5 Mar 2003, Bill Allombert wrote:
> > Why not use the modular algorithm of ZX_caract directly in QX_caract
> > instead of removing the content and calling ZX_caract ?
> [...]
> > Of course I have not addressed how to implement this, in particular
> > how to know we have a sufficiently large modulus.
> 
> For this to work, the result needs to be in Z[X], wich is not the current
> specification of QX_caract.

... or we know a multiple of the denominator, or we can use ratlift.
Furthermore I am specially interested by polred() in which this
assumption is correct.

> OK, this is implemented in CVS. The modulus bound is rigorous (~ Hadamard
> bound + floating point computation if bound is huge).

Thanks ! I have tried it and polred seems to be much faster on my degree
72 polynomials.

At least it use a bound of 2^16000 instead of 2^3000000 (72 times...).
Of course this is still much too large or else polred is a complete
failure (we expect polred to give small polynomial after all), but at
least this is bearable. (it take 9 minutes instead of 7 hours.)

Cheers,
Bill