polynomial over finite fields

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

Dear developers,

I am working on faster arithmetic for polynomial over finite field,
Currently we multiply using Kronecker trick of interpolating P(X,Y)
to P(X,X^n) for some sufficiently large n.

GEN
FpXQX_mul(GEN x, GEN y, GEN T, GEN p)
{
  pari_sp av = avma;
  GEN z, kx, ky;
  kx = mod_to_Kronecker(x,T);
  ky = mod_to_Kronecker(y,T);
  z = Kronecker_to_FpXQX(ZX_mul(ky,kx), T, p);
  return gerepileupto(av, z);
}

Note that n is chosen by looking solely at the maximum possible degree in
Y, not the actual degree. This is especially inefficient when x and y
coefficients are actually integers.

In particular, assume you are working with FpXQX mod S, where S has integer
coefficients. Then we will need to do a lot of reduction modulo S.
Unfortunately, in that case, Barrett reduction will not take advantage
of this property of S, and will be much slower than basecase reduction in
practice. However the Barrett inverse will also have integer coefficients.

If by chance the polynomial we need to reduce has also integer coefficients,
then we could change FpXQX_mul to do
  if (ZXX_is_ZX(x) && ZXX_is_ZX(y))
    return ZX_mul(x,y);

No what to do if it is not the case, i.e. y has integer coefficients but not 
x ?  One way would be to swap the variables and do a ZXY_ZX_mul, and swap back.

Cheers,
Bill.