Irreducible Polynomial

Author

Eric W. Weisstein
September 20, 2008

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

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

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

Examples

FactorList[#,Modulus->2]&/@{x^2,x^2+1,x^2+x+1}

IrreducibleQ[#,Modulus->2]&/@{x^2,x^2+1,x^2+x+1}

FactorList[#,Modulus->3]&/@{x^2,x^2+1,x^2+x+1,2x^2+x+1}

IrreducibleQ[#,Modulus->3]&/@{x^2,x^2+1,x^2+x+1,2x^2+x+1}

Counts

V6

L[q_,n_]:=Total[(Function[d,MoebiusMu[n/d]q^d]/@Divisors[n])/n]

Table[L[2,n],{n,10}]

Table[L[3,n],{n,10}]

IrreducibleQ[1,Modulus->2]

PolynomialQ[1]

V7

L[q_,n_]:=(1/n)DivisorSum[n,MoebiusMu[(n/(#))](q^(#))&]

L[q,n]

L[2,n]

Table[L[2,n],{n,10}]

Table[L[3,n],{n,10}]

Enumeration

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

polys[1]

(Table[Select[polys[n],IrreducibleQ[#,Modulus->2]&],{n,5}])//ColumnForm

Count[#,_?(IrreducibleQ[#,Modulus->2]&)]&/@(ipolys=Table[Select[polys[n],IrreducibleQ[#,Modulus->2]&],{n,10}])

Orders

Map[PolynomialOrder[#,x,Modulus->2]&,Take[ipolys,5],{2}]//Timing

Union/@Map[PolynomialOrder[#,x,Modulus->2]&,Take[ipolys,8],{2}]//Timing

Table[Position[Table[MultiplicativeOrder[2,n],{n,2^k-1}],k,1]//Flatten,{k,10}]//Timing

Table[Position[Table[MultiplicativeOrder[2,n],{n,2^k-1}],k,1]//Flatten,{k,15}]//Timing

Better Routine

?PolynomialOrder

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

PolynomialOrder[p_?PolynomialQ,Modulus->m_]:=Rest[FactorList[p,Modulus->m]]

PolynomialOrder[x^2+x+1,Modulus->3]

FactorList[2x^2+x+1,Modulus->2]

PolynomialOrder[(x^5)+x^2+1,x,Modulus->2]

FactorList[1,]

FactorList[(x^5)+x^2+1,Modulus->2]

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

PolynomialOrder[(x^5)+x^2+1,x,Modulus->2]

Divisors[2^5-1]