Finite Field

Author

Eric W. Weisstein
May 21, 2008

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

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

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

Code

<<FiniteFields`

PolyOrder[p_,x_]:=Module[{n=1},
While[!SameQ[Denominator[PolynomialMod[(x^n+1)/p,2]],1],n++];
n
]

BinaryPolys[1,x_]:={1,x}
BinaryPolys[n_,x_]:=Module[{k},
(1+x^n+Plus@@#)&/@Rest[Subsets[Table[x^k,{k,n-1}]]]
]

PrimitiveQ[p_,n_,x_]:=Module[
{e=Exponent[p,x]},
PolyOrder[p,x]==n^e-1
]

GF(2)

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

Select[polys[3],IrreducibleQ[#,Modulus->2]&]

Number of Degree n Irreducible Polynomials over GF(q)

L[n_,q_]:=Total[MoebiusMu[n/#]q^#&/@Divisors[n]]/n

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

(i=Table[Select[BinaryPolys[n,x],IrreducibleQ[#,2]&],{n,7}])//ColumnForm

Length/@i

Number of Degree n Primitive Polynomials over GF(q)

(p=Table[Select[BinaryPolys[n,x],PrimitiveQ[#,2,x]&],{n,7}])//ColumnForm

Length/@p

Map[IrreducibleQ[#,2]&,p,{2}]

Field Calculation (Attempts)

Irreducible[1,x]

GF[2,3]

IrreduciblePolynomial[x,2,3]

FieldIrreducible[GF[2,3],x]

ReduceElement[GF[2,3][{1,0,1,1}]]

ReduceElement[GF[2,3][{1,1,1,1}]]

?PowerList

PowerList[GF[2,3]]

ReduceElement[GF[2,3][#]]&/@Flatten[Outer[List,Sequence@@Table[{0,1},{4}]],3]

FullForm[%]

GF(6)

FieldIrreducible[GF[2,6],x]

IrreduciblePolynomial[x,2,6]

PowerList[GF[2,6]]

Union[ReduceElement[GF[2,6][#]]&/@Flatten[Outer[List,Sequence@@Table[{0,1},{7}]],6]]

NestList[Successor,GF[2,{0,0,0,0,0,0,0,0}][{1,1,0,0,0,0,1}],20]

NestList[Successor,GF[2,{1,1,0,0,0,0,1,0}][{1,1,1,1,1,1}],10]

ReduceElement/@%

ElementToPolynomial[#,x]&/@%

GF[2,{0,1,0,0,0,0,0,0}][{1,0,0,0,0,1,1,}]

PowerList[GF[2,6]]

GF[2,6][#]&/@%

ReduceElement/@%

Flatten[Outer[List,Sequence@@Table[{0,1},{6}]],5]

ReduceElement[GF[2,6][#]]&/@%

Union[%]

ReduceElement[GF[2,6][{1,1,0,1,0,1}]]

ReduceElement[GF[2,7][{1,0,0,0,0,1,1}]]

ReduceElement[GF[2,6][{1,1,0,0,0,0,1,1}]]

ElementToPolynomial[GF[2,6][{0,1,1,1,1,1,1}],x]

GF[2,6]//FullForm

ElementToPolynomial[GF[2,6][{1,1,1,1,0,1,1,0}],x]

Select[%424,ReduceElement[GF[2,6][#][[-1]]]

%//FullForm

ElementToPolynomial[GF[2,6],x]

GF[2,6][{1}]5

Successor[GF[2,{1,0,0,0,0,1,1}][{1,1,0,0,0,0,1}]]

ElementToPolynomial[%,x]

Reduce/@%

Length[%]

Union[%]

NestList[Successor[#]&,PolynomialToElement[GF[2,{1,0,0,0,0,1,1}],x^6+x+1],64]

Successor[GF[2,{1,1,0,0,0,0,1}][{1,0,0,0,0,1,1}]]

FullForm[%]

Successor[GF[2,{1,1,0,0,0,0,1}][{0,1,1,0,0,0,1}]]

ReduceElement[GF[2,{1,1,0,0,0,0,1}][{1,0,0,0,0,1,1}]]

Expand[(x^2+1)(x^4+1)]

Mod[%,2]

PolynomialToElement[GF[2],IrreduciblePolynomial[x,2,6]][[-1]]

IrreduciblePolynomial[x,2,6]

ElementToPolynomial[#,x]&/@NestList[Successor,PolynomialToElement[GF[2],x^6+x+1 ],3]

IrreduciblePolynomial[x,2,6]

p={1,0,0,0,0,1,1}

Successor[GF[2,{1,1,0,0,0,0,1}][%]]

%200//FullForm

%200[[-1]]

Successor[GF[2,{1,1,0,0,0,0,1}][%]]

Successor[GF[2,{1,1,0,0,0,0,1}][{1,1,0,0,0,1}]]

ElementToPolynomial[%,x]

PolynomialToElement[GF[2],x^6+x^4+x^2+x+1]

PolynomialToElement[GF[2,{],x^6+x^5+x^2+x+1]

PolynomialToElement[GF[2],1+(x^3)+(x^5)]

ReduceElement[PolynomialToElement[GF[2],(1+x)(1+x)]]

Successor[GF[2,{1,0 }]]

ElementToPolynomial[GF[2][{1,1,1}],x]

ReduceElement[PolynomialToElement[GF[2],x^2+1]]

ElementToPolynomial[%,x]

ElementToPolynomial[GF[2][(Subscript[{1}, 2])]x]

FieldIrreducible[GF[2],x]

FieldIrreducible[2,x]

?IrreduciblePolynomial*

SetFieldFormat

PowerList[GF[2]]