Basic Concepts from Probability, Complexity, Algebra and Number Theory - Introduction to Cryptography with Maple - page 106

> IrreduciblePolynomialsList := proc(p, n::posint, monic := true)
local coeffs, pols, interv;
global x;
x := 'x';
if monic then
interv := [$pˆn..2*pˆn - 1]
else
interv := [$pˆn..pˆ(n+1)-1]
end if;
coeffs := map(a -> convert(a, base, p), interv);
pols := map(l -> sort(sum(l[j]*xˆ(j-1), j=1..n+1)), coeffs);
#in Maple v.13 and above the preceding line may be replaced by the following:
#pols := map(l -> PolynomialTools:-FromCoefficientList(l,x), coeffs);
select(f -> Irreduc(f) mod p, pols)
end proc:

Example 2.25 Let us compute the monic irreducible polynomials of degree 4 in
Z 2 [

x ] (note that when p = 2 all nonzero polynomials are monic):

> IrreduciblePolynomialsList(2, 4);
[xˆ4 +x+1,xˆ4+xˆ3+1,xˆ4+xˆ3+xˆ2+x+1]

Z 2 [ ]

Similarly, the irreducible polynomials of degree 8 in x are:

> IrreduciblePolynomialsList(2, 8);
[xˆ8 + xˆ4 + xˆ3 +x+1,xˆ8+xˆ4+xˆ3+xˆ2+1,xˆ8+xˆ5+xˆ3+x+1,
xˆ8 + xˆ5 + xˆ3 + xˆ2 + 1, xˆ8 + xˆ5 + xˆ4 + xˆ3 + 1,
xˆ8+xˆ5+xˆ4+xˆ3+xˆ2+x+1,xˆ8+xˆ6+xˆ3+xˆ2+1,
xˆ8+xˆ5+xˆ3+x+1,xˆ8+xˆ6+xˆ5+x+1,xˆ8+xˆ6+xˆ5+xˆ2+1,
xˆ8 + xˆ6 + xˆ5 + xˆ3 + 1, xˆ8 + xˆ6 + xˆ5 + xˆ4 + 1,
xˆ8+xˆ6+xˆ5+xˆ4+xˆ2+x+1,xˆ8+xˆ6+xˆ5+xˆ4+xˆ3+x+1,
xˆ8+xˆ7+xˆ2+x+1,xˆ8+xˆ7+xˆ3+x+1,xˆ8+xˆ7+xˆ3+xˆ2+1,
xˆ8+xˆ7+xˆ4+xˆ3+xˆ2+x+1,xˆ8+xˆ7+xˆ5+x+1,
xˆ8 + xˆ7 + xˆ5 + xˆ3 + 1, xˆ8 + xˆ7 + xˆ5 + xˆ4 + 1,
xˆ8+xˆ7+xˆ5+xˆ4+xˆ3+xˆ2+1,xˆ8+xˆ7+xˆ6+x+1,
xˆ8+xˆ7+xˆ6+xˆ3+xˆ2+x+1,xˆ8+xˆ7+xˆ6+xˆ4+xˆ2+x+1,
xˆ8+xˆ7+xˆ6+xˆ4+xˆ3+xˆ2+1,xˆ8+xˆ7+xˆ6+xˆ5+xˆ2+x+1,
xˆ8+xˆ7+xˆ6+xˆ5+xˆ4+x+1,xˆ8+xˆ7+xˆ6+xˆ5+xˆ4+xˆ2+1,
xˆ8 + xˆ7 + xˆ6 + xˆ5 + xˆ4 + xˆ3 + 1]

Let us now consider an example in characteristic = 2; the monic irreducible

polynomials of degree 4 over Z 3 [ x ] are:

> IrreduciblePolynomialsList(3, 4);
[xˆ4 +x+2,xˆ4+2x+2,xˆ4+xˆ2+2,xˆ4+xˆ2+x+1,xˆ4+xˆ2+2x+1,
xˆ4 + 2xˆ2 + 2, xˆ4 + xˆ3 + 2, xˆ4 + xˆ3 + 2x + 1, xˆ4 + xˆ3 + xˆ2 + 1,
xˆ4+xˆ3+xˆ2+x+1,xˆ4+xˆ3+xˆ2+2x+2,xˆ4+xˆ3+2xˆ2 + 2x + 2,
xˆ4 + 2xˆ3 + 2, xˆ4 + 2xˆ3 +x+1,xˆ4+2xˆ3 + xˆ2 + 1,
xˆ4 + 2xˆ3 + xˆ2 +x+2,xˆ4+2xˆ3 + xˆ2 + 2x + 1, xˆ4 + 2xˆ3 + 2xˆ2 +x+2]

These results may be compared with the listing in [131, Table C].

In the previous examplewe have considered irreducible polynomials of lowdegree
but, as we will see in Chap. 5 , an irreducible polynomial of degree 128 is used in the
CMAC authentication scheme. The list of irreducible polynomials of degree 128 in
Z 2 [

is way too long to be displayed here, but we will give a procedure to find a
single irreducible polynomial of a given degree. This procedure takes as input the
prime p and the degree n and returns the first irreducible polynomial of

x ]

in
the enumeration implicitly defined in IrreduciblePolynomialsList , i.e.,

Z p [ x ]