Cryptography Reference
In-Depth Information
Z
p
[
]
+
(
)
={
+
|
∈
(
)
}
Z
p
[
]
f
ideal of
x
generated by
f
and
g
f
g
k
k
f
. The rings
x
Z
p
[
]
/(
)
and
x
f
are canonically isomorphic, with isomorphism given by the map
from the former to the latter. Thus both rings are essentially the same
and we will usually work with the former since its elements (polynomials) require
less notation.
2. Note that, although we will only need to work with the rings
g
→[
g
]
in order to
build the fields of order
p
n
, all the preceding constructions and results are valid,
more generally, for any polynomial ring
k
Z
p
[
x
]
[
x
]
, with
k
a field.
We need something else in order to obtain a field from this construction. Example
2.23 shows that, as in the case of
]
f
may fail to be a field due to the existence
of zero divisors. In fact, the non-existence of zero divisors is, in this case, not only
necessary but also sufficient for
Z
q
,
Z
p
[
x
]
f
to be a field. Indeed, as the following exercise
shows, any finite integral domain is a field (see also [131, Theorem 1.31]).
Z
p
[
x
Exercise 2.33
Show that a finite integral domain
R
is a field. To prove it, consider a
nonzero element
a
R
and show that themap from
R
to itself given bymultiplication
with
a
is injective. Show that this map is also surjective (and hence a bijection) and
use it to prove that
a
is an invertible element of
R
. (The same argument shows, more
generally, that any non-zero divisor in a finite commutative ring with 1 is invertible.)
∈
It is clear then that, for
Z
p
[
x
]
f
to be a field, the product in
Z
p
[
x
]
of two poly-
nomials of
Z
q
,wesee
that
f
must satisfy a property similar to primality. This property is the following:
Z
p
[
x
]
f
cannot be equal to
f
. Thus, as in the construction of
Definition 2.25
A polynomial
f
∈ Z
p
[
x
]
is said to be
irreducible
if deg
(
f
)>
0
and
f
cannot be written as a product
f
=
gh
, where
g
,
h
∈ Z
p
[
x
]
and deg
(
g
)
,
deg
(
h
)>
0.
Examples 2.4
1. Constant polynomials are not irreducible but all polynomials of degree 1 are
irreducible by Proposition 2.10.
2. If deg
2 or 3 then
f
is irreducible if and only if
f
does not have zeros in
k
. Indeed, using Proposition 2.10 we see that the irreducibility of
f
is, in this
case equivalent to not having any degree 1 factor, i.e., to the non-existence of a
polynomial
g
such that deg
(
f
)
=
(
g
)
=
1 and
g
|
f
. But, by Theorem 2.21 this is, in
turn, equivalent to
f
not having zeros in
k
.
3. The only irreducible polynomial of degree 2 in
is
x
2
1 because neither
0 nor 1 is a zero while, on the other hand, the remaining three polynomials of
degree 2 (namely,
x
2
,
x
2
Z
2
[
x
]
+
x
+
x
,
x
2
Z
2
. Similarly, it can
easily be checked that the only irreducible polynomials of degree 3 in
+
+
1) all have zeros in
Z
2
[
x
]
are
x
3
1,
x
3
x
2
+
x
+
+
+
1.
Now, suppose that we want to find all the irreducible polynomials of a given
degree over
Z
p
. If the degree is greater than 3, then we cannot use the criterion
given in Example 2.4 but we can check whether a polynomial is irreducible or not
by dividing it by the irreducible polynomials of smaller degree (or we can generate
