Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: primitive polynomials

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

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


Here is code adopted from

http://forums.wolfram.com/mathgroup/archive/1998/Nov/msg00194.html

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[
   {fax},
   If [!PrimeQ[p] || !PolynomialQ[poly,x] || Variables[poly]=!={x},
     Return[False]];
   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.

<<Algebra`

isPrimitive[x_, poly_, p_, deg_] := Catch[Throw[Module[
   {fax=(p^deg-1)/Map[First,FactorInteger[p^deg-1]]},
   For [j=1, j<=Length[fax], j++,
     If [PolynomialPowerMod[x,fax[[j]],{poly,p}]===1, Throw[False]];
     ];
   True
   ]]]

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

http://forums.wolfram.com/mathgroup/archive/2003/Mar/msg00494.html


Daniel Lichtblau
Wolfram Research

• References:
  • primitive polynomials
    • From: "xxxxyz@abv.bg" <xxxxyz@abv.bg>