Products of Polynomials

Q: I am computing large numbers of products of high-degree polynomials mod prime , but the generic PolynomialMod function is too slow. How can I speed up this process?

A: Daniel Lichtblau (danl@wolfram.com) answers: There is fast dedicated technology built into the Algebra` context for manipulating dense univariate polynomials, represented by coefficient lists, modulo .

The one you want is PolynomialTimesModList.

Start with code to generate random polynomials modulo some given (which need not be prime).

Construct a pair of degree 1200 random polynomials.

Multiply them using PolynomialMod.

Converting to coefficient lists, multiplying, and converting back is much faster.

Check the results for consistency.

Generally speaking, you would want to do as much of the computation as possible using the list representation, and only convert from and to explicit polynomials, if at all, at the beginning and end of the process.