Efficient implementation of polynomial multiplication

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

Hash: SHA1


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

Version: GnuPG v1.2.3 (GNU/Linux)


More information about the gmp-discuss mailing list