Fast multiplication of polynomials mod p

*To*: mathgroup at smc.vnet.net*Subject*: [mg50985] Fast multiplication of polynomials mod p*From*: lzwnews at yahoo.com (Trav)*Date*: Fri, 1 Oct 2004 04:47:59 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

I'm running a huge job on Mathematica, and the bulk of the running time is used on computing products of polynomials mod prime p (the program has to handle hundreds of polynomials of degrees up to hundreds, maybe even a 1000, mod p). The generic PolynomialMod function is slow (at O(d^2), d being the degree). Is there any add-on to speed up this process? I do know there's a 'FiniteFields' package, but any other recommendations? [ I just realized that I need to perform Gaussian elimination mod p as well. And the matrix is not sparse. Is there a good Mathematica library for that? ] Thanks in advance.

**Follow-Ups**:**Re: Fast multiplication of polynomials mod p***From:*Daniel Lichtblau <danl@wolfram.com>

**Re: Fast multiplication of polynomials mod p***From:*Andrzej Kozlowski <akoz@mimuw.edu.pl>