Re: Speed up {Flx,FpX,FpXQX}_divrem_basecase for suitable polynomials

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

On Tue, Sep 08, 2015 at 11:47:30AM +0200, Peter Bruin wrote:
> Bonjour,
> 
> When computing with non-prime finite fields, one is often free to choose
> a defining polynomial f (of some given degree n) over the prime field.
> If we write f in the form c*X^n + f1 with deg(f1) < n, then for division
> with remainder modulo f, it "should be" best to take deg(f1) as small as
> possible.  However, the current code for division with remainder in PARI
> does not yet give an advantage in that case.
> 
> The attached patch modifies the functions {Flx,FpX,FpXQX}_divrem_basecase
> and Flx_rem_basecase in order to reduce the complexity of computing the
> (quotient and) remainder of g by f from O((deg g - deg f)(deg f)) to
> O((deg g - deg f)(deg f1)).

Hello Peter, are you still interest in this topic ?

You patch only covers the basecase, however the Barrett reduction method
more or less takes advantage of deg(f1) being small already 
because this leads to a Barrett inverse with a special shape: 1/c+x^h*f2
with deg(f2) small (and h large).

So the functions F*_get_red could be changed to detect this situation
and use a different threshold in this case.

What do you think ?

Cheers,
Bill.