Re: Faster exponentiation in some extensions of finite fields of small characteristics

[Peter Bruin <P.J.Bruin@math.leidenuniv.nl>]

Hello Bill,

> On Fri, Jan 15, 2016 at 06:35:06PM +0100, Peter Bruin wrote:
>> Hello Jean-Pierre,
>> 
>> > May I ask why you reverse the array of coeffs when packing it into
>> > an integer in the kron_pack_Flx_spec functions you added?  Do the
>> > fromdigits function reverse it another time?
>> 
>> Yes, the reason is the existing convention for fromdigits.  I did not
>> want to write another copy of fromdigits with the only difference
>> being the order of the digits.  I did not try to to find out whether
>> this would give a noticeable speed improvement.
>
> Is kron_pack_Flx_spec actually useful ? 
>
> Polynomial multiplication is independent of coefficients order, so it
> is not necessary to repack. Indeed Flx_mulspec_mulii does not do it:
>
> INLINE GEN
> Flx_mulspec_mulii(GEN a, GEN b, ulong p, long na, long nb)
> {
>   GEN z=muliispec(a,b,na,nb);
>   return int_to_Flx(z,p);
> }

The problem is that when lower-degree polynomial coefficients are packed
into the most significant words of integers, then these coefficients
will disappear if they are zero, e.g. the polynomials 1 and x are both
converted to the integer 1.  The function Flx_mulspec solves this by
shifting the polynomials such that the constant coefficient is non-zero,
but we cannot easily do this for FlxqM_mul_Kronecker because of the
additions in ZM_mul.  (There may also be a problem with composite moduli
in Flx_mul, I didn't check.)

Peter