Efficient implementation of polynomial multiplication

[Décio Luiz Gazzoni Filho]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hello,

I'm working on a project using GMP, and I'm stuck trying to make a fast 
routine for multiplying polynomials (with coefficients from Z/pZ, i.e. the 
size of the coefficients is bounded.) The technique I'm used is called 
`binary segmentation' and consists of evaluating the polynomials f(x), g(x) 
at x = 2^b, with b > p^2*max(deg(f),deg(g)) so that there's no risk of carry 
from one polynomial coefficient to the other. So here's how the resulting 
integers f(2^n) = a0 + a1*2^n + a2*2^(2n) + ... and g(2^n) = b0 = b1*2^n + 
b2*2^(2n) + ... look like (sorry for the ASCII art):


0              n             2n
a0   00...00   a1  00...00   a2   00...00 ...
b0   zero-pad  b1  zero-pad  b2   zero-pad ...

So my question, what is the most efficient way of building this integer (and 
later removing coefficients from it at the same 0,n,2n,... boundaries), while 
still being portable? Of course I could use lshifts and adds to insert the 
coefficients, and mpz_fdiv_r_2exp and rshifts to remove them, but this is 
hopelessly slow: my routine spends the bulk of its time doing the shifts.

I'm thinking either something that manipulates the mpz_t->_mp_d array 
directly, or something using mpz_import/mpz_export... anyway, I hope someone 
on the list can help me with this.

I was going to put my current code here, but as it stands it's not generating 
meaningful results.

Thanks for the help

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQFASKcPFXvAfvngkOIRAlh6AJ9cPhPv8l8ie9F0Gtn8vJTpHrW08wCgg6Yd
gsFW4mz0DZYPiV42Zo1yp2E=
=+UnQ
-----END PGP SIGNATURE-----