Cryptography Reference
In-Depth Information
where
n
is a positive integer (i.e., the degree of
p
(
x
)
, denoted as
deg
(
p
)
), the
coefficients
a
i
(0
≤
i
≤
n
)
are elements in
A
, and
x
is a symbol not belonging
to A.
The set of all polynomials over
A
is denoted by
A
[
x
]. The elements of
A
[
x
]
are polynomials, and one can compute with these polynomials as if they were
integers. More specifically, one can add and multiply polynomials. Furthermore, if
f, g
∈
A
[
x
] such that
g
=0, then one can write
f
=
gq
+
r
for
q, r
A
[
x
] and
deg
(
r
)
<deg
(
g
). This equation reminds us of Euclid's division
theorem (see Theorem 3.3), and hence we can also apply the Euclidean algorithms in
A
[
x
]. In this case,
r
is the remainder of
f
divided by
g
, denoted by
r
∈
f
(mod
g
).
The set of all remainders of all polynomials in
A
[
x
] modulo
g
is denoted by
A
[
x
]
g
.
A polynomial
f
≡
∈
A
[
x
] is
irreducible
over
A
if the following two conditions
are satisfied:
1.
f
has a positive degree;
2.
f
=
gh
with
g, h
∈
A
[
x
] implies that either
g
or
h
is a constant polynomial.
Otherwise,
f
is
reducible
over
A
. Note that the reducibility of a polynomial
depends on the algebraic structure
A
over which the polynomial is defined (i.e.,
a polynomial can be reducible over one algebraic structure and irreducible over
another).
Against this background, one can show that if
F
is a field and
f
is a nonzero
polynomial in
F
[
x
],then
F
[
x
]
f
is a ring. Furthermore, one can show that
F
[
x
]
f
is a
field if and only if
f
is irreducible over
F
. In this case, the number of elements in the
field
F
[
x
]
f
is
p
n
(if
p
represents the number of elements in
F
and
n
represents the
degree of
f
). We conclude that for every prime
p
and every positive integer
n
,there
is a finite field with
p
n
elements (as mentioned in Section 3.1.2.5), and we denote
this field by
F
p
[
x
]
f
. Under isomorphism, we can say that
F
p
[
x
]
f
is the finite field of
order
p
n
.
For example, the polynomial
f
(
x
)=
x
8
+
x
4
+
x
3
+
x
+1is irreducible over
F
2
. Consequently, the set of all polynomials modulo
f
over
F
2
forms a field with 2
8
elements (i.e., all polynomials over
F
2
of degree less than 8). So any element in the
field
F
2
[
x
]
f
is of the form
b
7
x
7
+
b
6
x
6
+
b
5
x
5
+
b
4
x
4
+
b
3
x
3
+
b
2
x
2
+
b
1
x
+
b
0