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>