Peter Bruin on Mon, 18 Jan 2016 11:57:15 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Faster exponentiation in some extensions of finite fields of small characteristics |
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