Cryptography Reference
In-Depth Information
Z
2
[
]
Exercise 2.32
Consider the polynomial ring
and give examples that show
that a polynomial of degree 2 can have two zeros, one zero (which then will have
multiplicity 2) or no zeros.
x
2.8.3 The Field of p
n
Elements
We are now ready to construct, given a prime power
p
n
, a field of
p
n
elements. The
construction will be very similar to the one used to obtain
Z
p
from the integers but,
in this case, the starting point will be
Z
p
[
x
]
instead.
So, suppose that
f
∈ Z
p
[
x
]
is a polynomial with deg
(
f
)
=
n
>
0. We define
aset
Z
p
[
x
]
f
={
g
∈ Z
p
[
x
]|
deg
(
g
)<
deg
(
f
)
}
which is the analogue of
Z
q
,
for
q
1. Indeed, while the latter set consists of the possible remainders of
integer division by
q
, the former consists of all the possible remainders of polynomial
division by
f
. Note that
∈ Z
,
q
>
a
n
−
1
x
n
−
1
Z
p
[
x
]
f
={
+ ··· +
a
1
x
+
a
0
|
a
i
∈ Z
p
}
,so
p
n
. We define two binary operations on
that
|Z
p
[
x
]
f
|=
Z
p
[
x
]
f
by
g
+
h
=
(
g
+
h
)
mod
f
,
gh
=
(
gh
)
mod
f
, i.e., the operations in
Z
p
[
x
]
f
are the same as
the corresponding operations in
Z
p
[
x
]
followed by taking the remainder of division
.
8
In fact, adding two polynomials of
by
f
in
Z
p
[
x
]
Z
p
[
x
]
f
gives the same result as
adding them in
,sothatthe'mod
f
' is not necessary in the case of addition but
we have written the operation this way to emphasize the fact that these operations are
defined exactly like the operations of
Z
p
[
x
]
Z
q
: in order to add/multiply two polynomials
Z
p
[
]
f
, we just add/multiply them in
Z
p
[
]
in
x
x
and then we reduce modulo
f
.
]
f
with these two operations is a commutative ring with
identity. The proof is straightforward and
It is easily seen that
Z
p
[
x
Z
p
[
x
]
f
inherits the ring properties from
Z
p
[
x
]
similarly to the way
Z
q
inherits them from
Z
. But observe that
Z
p
[
x
]
f
need
not be a field:
x
2
Example 2.23
Let
p
=
2 and
f
=
+
1
∈ Z
2
[
x
]
. Then
Z
2
[
x
]
f
is not a field
because the element
x
+
1
∈ Z
2
[
x
]
f
is a zero divisor and hence it does not have an
x
2
x
2
Z
2
[
]
f
,
(
+
)(
+
)
=
(
+
)
(
+
)
=
inverse. Indeed, we see that in
x
x
1
x
1
1
mod
1
0.
Remarks 2.4
1. The ring
Z
p
[
x
]
f
is constructed from
Z
p
[
x
]
just as
Z
q
is constructed from
Z
.This
ring can also be built in a way similar to the construction of
, i.e.,
as a quotient ring whose elements are congruence classes modulo
f
(also called
a residue class ring). These classes are defined, using the divisibility properties
of
Z
/
n
Z
from
Z
Z
p
[
x
]
, in a similar way to congruence classes modulo a positive integer in
Z
:
given
g
,
h
∈ Z
p
[
x
]
, we say that
g
≡
h
(
mod
f
)
if and only if
f
|
g
−
h
. Then,
if we denote the congruence class of
g
∈ Z
p
[
x
]
by
[
g
]
,weset
Z
p
[
x
]
/(
f
)
=
{[
g
]|
g
∈ Z
p
[
x
]} = {
g
+
(
f
)
|
g
∈ Z
p
[
x
]}
, where
(
f
)
={
hf
|
h
∈ Z
p
[
x
]}
is the
8
We are committing here the usual abuse of notation and using the same generic symbols for
different additions and different multiplications.
