Cryptography Reference
In-Depth Information
(
)
the irreducible polynomial
f
such that the value of
f
p
is the lowest among all the
(
)
values
g
with
g
irreducible of degree
n
. Of course, this procedure can easily be
modified to find not just one but any given number of irreducible polynomials instead
(provided that the specified number is less than the total number of irreducible poly-
nomials of the given degree). The function that finds the first irreducible polynomial
is the following:
p
> IrreduciblePolynomial := proc(p, n::posint)
local a, coeffs, f, found;
global x;
a := pˆn;
x := 'x';
found := false;
while not found do
coeffs := convert(a, base, p);
f := sum(coeffs[j]*xˆ(j-1), j=1..n+1);
found := Irreduc(f) mod p;
a:=a+1
end do;
sort(f)
end proc:
Example 2.26
Let us find the first irreducible polynomial of degree 128 in
Z
2
[
x
]
,
which is the one used in the CMAC scheme:
> IrreduciblePolynomial(2, 128);
xˆ128 + xˆ7 + xˆ2 +x+1
Of course, using Maple it is easy to find irreducible polynomials of even larger
degree.
Exercise 2.34
(i) Write a Maple procedure that finds the first ten monic irreducible polynomials
in
of a given degree
n
(or the whole list of monic irreducible polynomials
if there are fewer than ten).
(ii) Write a Maple procedure that finds the “last” irreducible polynomial in
Z
p
[
x
]
Z
p
[
x
]
of degree
n
, i.e., the irreducible polynomial
f
of degree
n
for which
f
(
p
)
is
largest.
As can be easily guessed from our previous comments, irreducible polynomials
allow us to build finite fields of order
p
n
:
Theorem 2.22
Let f
∈ Z
p
[
x
]
. Then the ring
Z
p
[
x
]
f
is a field if and only if f is
irreducible.
Proof
The proof is the same as the one that
Z
q
is a field if and only if
q
is prime,
except that this time we work with polynomials of
and with the (extended)
Euclidean algorithm for polynomials. We have already noted that the irreducibility
of
f
Z
p
[
x
]
is a necessary condition for
Z
p
[
x
]
f
to be a field because if
f
is not irre-
ducible, then any factor
g
of
f
such that 0
<
deg
(
g
)<
deg
(
f
)
is a zero divisor in
Z
p
[
x
]
f
. Conversely, if
f
is irreducible and
g
a nonzero polynomial in
Z
p
[
x
]
f
, then
