Cryptography Reference
In-Depth Information
all the reducible polynomials of a given degree by multiplying all polynomials of
smaller degree). This method is rather inefficient when the degree is large, and there
are more powerful methods to check the irreducibility of a polynomial, but we shall
not go into the details as they are not needed for our purposes. We will show instead
how we can compute the irreducible polynomials (of a given degree) over a prime
field using Maple.
The Maple function that tests whether a polynomial over a prime field is irre-
ducible is
Irreduc
which, when used together with the operator
mod
in the form
Irreduc(f) mod p
(where
f
is the polynomial to be tested and
p
the prime
that defines the field of coefficients) returns
true
if the polynomial
f
∈ Z
p
[
x
]
is
irreducible and
false
otherwise.
Example 2.24
Let us check the irreducibility of a couple of polynomials of
Z
2
[
x
]
.
We have :
> Irreduc(xˆ8 + xˆ4 + xˆ3 +x+1)mod2;
true
while, on the other hand:
> Irreduc(xˆ8 + xˆ4 + xˆ2 +x+1)mod2;
false
This shows that the first of these polynomials of
is irreducible while the
second is not. We can also obtain the irreducible factors of the latter polynomial by
computing:
Z
2
[
x
]
> Factor(xˆ8 + xˆ4 + xˆ2 +x+1)mod2;
(xˆ4 + xˆ3 + xˆ2 + x + 1)(xˆ4 + xˆ3 + 1)
This also shows that not having any zeros in the coefficient field is not a sufficient
condition for a polynomial to be irreducible. It is easy to check that the polynomial
x
8
x
4
x
2
+
+
+
x
+
1
∈ Z
2
[
x
]
has no zeros in
Z
2
but, as we have just seen, this
polynomial is not irreducible.
Next we give a procedure to compute all the irreducible polynomials of a given
degree over a prime field. In practice, one is usually interested in the monic irre-
ducible polynomials because any irreducible polynomial has a unique associated
monic irreducible polynomial which is obtained just by multiplying the original
polynomial by the inverse of its leading coefficient. This is a similar situation to the
one arising when we consider the primes, i.e., the “positive irreducibles” of
(the
negative irreducibles are obtained from the primes just as the non-monic irreducible
polynomials are obtained from the monic ones: by multiplying by a unit of the ring).
The next function takes as input a prime
p
which defines the coefficient field, a
positive integer
n
which specifies the degree, and an optional parameter
monic
which
is
true
by default. The output is the list of all the monic irreducible polynomials
of
Z
of degree
n
or, if the argument
false
is passed to
monic
, the list of all
irreducible polynomials.
Z
p
[
x
]
