# Efficient implementation of polynomial multiplication

Décio Luiz Gazzoni Filho decio at decpp.net
Fri Mar 5 13:12:56 CET 2004

```-----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 ...

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)