Cryptography Reference
In-Depth Information
Then use these maps to define the multiplication as a function that assigns to a pair
of elements of
{
,
,
,
}
another element of this set (their product). Use
tabl
to
compute the table of this multiplication and verify that it is the one given above.
0
1
2
3
The multiplication
mult4
defined above looks very similar to the multiplication
in
Z
n
, except that now we multiply polynomials and take the remainder of dividing
by
x
2
1 which plays here the role of the modulus
n
. The similarity goes further
because the four polynomials 0
+
x
+
,
1
,
x
,
x
+
1 are the possible remainders of dividing a
polynomial by
x
2
Z
n
are the possible remainders of
integer division by
n
(we are assuming that all these polynomials have coefficients
in
+
x
+
1 just like the elements of
Z
2
). We have seen before that the order of a finite field is always a prime power and,
by generalizing this construction we are going to show that, for each prime power
p
n
there is a field of order
p
n
(which, moreover, is unique up to isomorphism).
2.8.2 The Polynomial Ring
Notations and terminology
. We will adopt the standard terminology and notational
conventions for polynomials. For example, if there is no ambiguity about the name
of the variable, we will write
f
instead of
f
(
)
to denote a polynomial. The zero
polynomial is the polynomial whose coefficients are all equal to 0 and is denoted
simply by 0. Moreover, we follow the convention that a term of the form
a
i
x
i
with
a
i
x
=
i
=
0
a
i
x
i
=
0 need not be written down, so a generic nonzero polynomial
f
∈
can always be written as a sumof polynomials—called
monomials
—of the form
a
i
x
i
with
a
i
R
[
x
]
=
i
=
0
a
i
x
i
with
a
n
=
0. If
f
=
0, then
f
=
0 and
a
n
is called the
leading coefficient
of
f
and
n
the
degree
of
f
, denoted
n
=
deg
(
f
)
.If
f
=
0 then,
by convention, we write deg
(
f
)
=−∞
(and we also agree to the conventions that
−∞
<
n
,
−∞ + −∞ = −∞
and
−∞ +
n
=−∞
, for each integer
n
).
a
0
is
the
constant term
of
f
and if
f
0,
f
is called
a
constant polynomial
. The polynomials whose leading coefficient is 1 are called
monic polynomials
. We see that
f
is a monomial precisely when all the coefficients
of
f
, except the leading coefficient, are equal to 0.
Let
R
be a commutative ring with identity and
f
=
a
0
or, equivalently, if deg
(
f
)
≤
,
g
∈
R
[
x
]
. We can write
f
=
i
=
0
a
i
x
i
,
g
=
i
=
0
b
i
x
i
and define their sum:
n
x
i
f
+
g
=
0
(
a
i
+
b
i
)
.
i
=
=
i
=
0
a
i
x
i
and
g
=
i
=
0
b
i
x
i
The product of
f
is the polynomial:
n
+
m
k
c
k
x
k
fg
=
,
where
c
k
=
a
i
b
k
−
i
,
for 0
≤
k
≤
n
+
m
.
k
=
0
i
=
0
