MathGroup Archive 2005

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

Search the Archive

Re: primitive polynomials

  • To: mathgroup at
  • Subject: [mg55902] Re: [mg55866] primitive polynomials
  • From: Daniel Lichtblau <danl at>
  • Date: Sat, 9 Apr 2005 03:55:59 -0400 (EDT)
  • References: <>
  • Sender: owner-wri-mathgroup at

xxxxyz at wrote:
> Hi,
> How can I check if a given polynomial is primitive in GF(2)?
> Thanks.

Here is code adopted from

We assume at the start that the polynomial is irreducible modulo the 
prime in question. That can be tested as below.

isIrreducible[x_, poly_, p_] := Module[
   If [!PrimeQ[p] || !PolynomialQ[poly,x] || Variables[poly]=!={x},
   fax = FactorList[poly,Modulus->p];
   Length[fax]==2 && fax[[2,2]]==1

For primitive testing we need to know if powers of x are equivalent to 1 
modulo certain factors of p^degree-1, where degree is the degree of the 
polynomial in question.


isPrimitive[x_, poly_, p_, deg_] := Catch[Throw[Module[
   For [j=1, j<=Length[fax], j++,
     If [PolynomialPowerMod[x,fax[[j]],{poly,p}]===1, Throw[False]];

Here is an example from the note at that URL. We work modulo 293. For 
your situation you would set the 'p' parameter to 2.

p = 293;
deg = 15;

poly = 38 + 117*x + 244*x^2 + 234*x^3 + 212*x^4 + 142*x^5 + 103*x^6 +
   60*x^7 + 203*x^8 + 124*x^9 + 183*x^10 + 96*x^11 + 225*x^12 +
   123*x^13 + 251*x^14 + x^15;

First we'll check that it is irreducible (it is, because as per that 
note it was manufactured in such a way as to be irreducible).

In[14]:= isIrreducible[x,poly,p]
Out[14]= True

In[15]:= isPrimitive[x,poly,p,deg]
Out[15]= False

So this is not a primitive polynomial. Note that we can construct such a 
polynomial by testing, instead of x, terms such as x+1, x+2,...

In[16]:= isPrimitive[x+1,poly,p,deg]
Out[16]= False

In[17]:= isPrimitive[x+2,poly,p,deg]
Out[17]= True

This shows x+2 is a primitive root, hence x will be primitive root for 
poly with x replaced by x-2.

poly2 = poly /. x->x-2;

In[19]:= isPrimitive[x,poly2,p,deg]
Out[19]= True

In addition to the above URL there is information on finite field 
polynomial manipulation at

Daniel Lichtblau
Wolfram Research

  • Prev by Date: Re: Having trouble with substitution tile at higher iteration levels--> takes forever!
  • Next by Date: Re: Replacement gyrations
  • Previous by thread: primitive polynomials
  • Next by thread: Sorting complex points