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.

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

```

• 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