Primitive Polynomial

Author

Eric W. Weisstein
April 14, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Algebra/PrimitivePolynomial.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/PrimitivePolynomial.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Initialization

<<Algebra`PolynomialPowerMod`

Code

PolynomialOrder[p_,x_]:=Module[{n=1},
While[
PolynomialRemainder[x^n+1,p,x,Modulus->2]=!=0,n++];
n
]

PrimitiveQ[p_,x_]:=PolynomialOrder[p,x]==2^Exponent[p,x]-1

Polynomial[l_List,x_]:=Fold[x#1+#2&,0,l]

polys[1]:={x+1}
polys[n_]:=(Expand[Polynomial[Join[{1},#,{1}],x]])&/@Flatten[Outer[List,Sequence@@Table[{0,1},{n-1}]],n-2]

Counts

Table[Select[polys[n],PrimitiveQ[#,x]&],{n,5}]//ColumnForm

Table[Count[polys[n],_?(PrimitiveQ[#,x]&)],{n,8}]//Timing

Table[Count[polys[n],_?(PrimitiveQ[#,x]&)],{n,9,9}]//Timing

Table[EulerPhi[2^n-1]/n,{n,10}]

Example

PolynomialOrder[x^2+x+1,x]

Table[Through[{PolynomialQuotient,PolynomialRemainder}[x^n+1,x^2+x+1,x,Modulus->2]],{n,3}]