Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Fast multiplication of polynomials mod p

• To: mathgroup at smc.vnet.net
• Subject: [mg51036] Re: [mg50985] Fast multiplication of polynomials mod p
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Sat, 2 Oct 2004 03:18:17 -0400 (EDT)
• References: <200410010847.EAA11443@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Trav wrote:
> 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.


There is fast dedicated technology built into the Algebra` context for 
manipulating dense univariate polynomials, represented by coefficient 
lists, modulo p. Here are the functions (they all are named 
Polynomial...List).

In[2]:= ??Algebra`Polynomial*List
Algebra`PolynomialDerivativeModList  Algebra`PolynomialPlusModList
Algebra`PolynomialDivisionModList    Algebra`PolynomialPowerModList
Algebra`PolynomialExtendedGCDModList Algebra`PolynomialPthRootModList
Algebra`PolynomialFactorModList      Algebra`PolynomialQuotientModList
Algebra`PolynomialGCDModList         Algebra`PolynomialRemainderModList
Algebra`PolynomialMakeMonicModList   Algebra`PolynomialSubtractModList
Algebra`PolynomialMinusModList       Algebra`PolynomialTimesModList

The one you want is PolynomialTimesModList. To get an idea of speed I'll 
show a brief demo. We start with code to generate random polynomials 
modulo some given p (which actually need not be prime). We'll multiply a 
pair of degree over 1000.

randomPoly[deg_, mod_, x_] :=
   Table[Random[Integer,mod-1],{deg+1}] . x^Range[0,deg]

deg = 1200;
SeedRandom[1234];
p = Prime[1234];
poly1 = randomPoly[deg, p, x];
poly2 = randomPoly[deg, p, x];

Now let's see what PolynomialMod does.

In[9]:= Timing[prod1 = PolynomialMod[poly1*poly2,p];]
Out[9]= {5.61 Second, Null}

We can convert to lists, multiply, and convert back quite a bit faster.

In[10]:= Timing[
   listpoly1 = CoefficientList[poly1,x];
   listpoly2 = CoefficientList[poly2,x];
   prod2list = Algebra`PolynomialTimesModList[listpoly1,listpoly2,p];
   prod2 = prod2list . x^Range[0,Length[prod2list]-1];
   ]
Out[10]= {0.03 Second, Null}

We check the results for consistency.

In[11]:= prod1===prod2
Out[11]= True

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


Gaussian elimination with integer matrices modulo p can be done via

RowReduce[matrix, Modulus->p]


Daniel Lichtblau
Wolfram Research

• References:
  • Fast multiplication of polynomials mod p
    • From: lzwnews@yahoo.com (Trav)