Bill Allombert on Wed, 5 Mar 2003 21:44:18 +0100

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



Why not use the modular algorithm of ZX_caract directly in QX_caract 
instead of removing the content and calling ZX_caract ?

The new LLL allows for polred() of polynomials of large degree/coefs and
now the QX_caract step is the most consuming. 

A simple example:

? polred(x^20+2^16)[13]
%5 = x^20 + 16

This polynomial is the result of
QX_caract(x^20 + 65536,1/32768*x^19,x)
%6 = x^20 + 16

which in turn lead to
ZX_caract(x^20 + 65536,x^19,x)
%7 = x^20 + 32592575621351777380295131014550050576823494298654980010178247189670100796213387298934358016

This lead to a modular computation with a final modulus of 324bits when
using a direct modular approach, a final modulus of 6 bits would have
lead to the correct result.

This is especially true in polred, since the polynomials we get are
expected to be small.

Of course I have not addressed how to implement this, in particular
how to know we have a sufficiently large modulus.