Cryptography Reference
In-Depth Information
where the
coe
7
cients
a
j
are in
R
for
j
0 and
a
j
= 0 for all but a finite
number of those values of
j
. The set of all such polynomials is denoted by
R
[
x
].
If
a
n
≥
= 0, and
a
j
= 0 for
j>n
, then
a
n
is called the
leading coe
7
cient
of
f
(
x
).
If the leading coeGcient
a
n
=1
R
, in the case where
R
is a commutative ring
with identity 1
R
, then
f
(
x
) is said to be
monic
.
We may add two polynomials from
R
[
x
],
f
(
x
)=
j
=0
a
j
x
j
and
g
(
x
)=
j
=0
b
j
x
j
,by
f
(
x
)+
g
(
x
)=
∞
(
a
j
+
b
j
)
x
j
∈
R
[
x
]
,
j
=0
and multiply them by
f
(
x
)
g
(
x
)=
∞
c
j
x
j
,
j
=0
where
j
c
j
=
a
i
b
j
−
i
.
i
=0
Also,
f
(
x
)=
g
(
x
) if and only if
a
j
=
b
j
for all
j
=0
,
1
,...
. Under the above
operations
R
[
x
]is a ring, called the
polynomial ring over
R
in the indeterminant
x
. Furthermore, if
R
is commutative, then so is
R
[
x
], and if
R
has identity 1
R
,
then 1
R
is the identity for
R
[
x
]. Notice that with these conventions, we may
write
f
(
x
)=
j
=0
a
j
x
j
, for some
n
∈
N
, where
a
n
is the leading coeGcient
since we have tacitly agreed to “ignore” zero terms.
If
α
R
, we write
f
(
α
) to represent the element
j
=0
a
j
α
j
R
, called the
substitution
of
α
for
x
. When
f
(
α
) = 0, then
α
is called a
root
of
f
(
x
). The
substitution gives rise to a mapping
∈
∈
f
:
R
→
R
given by
f
:
α
→
f
(
α
)
,
which is determined by
f
(
x
). Thus,
f
is called a
polynomial function
over
R
.
Definition A.32
(
Degrees of Polynomials
)
If
f
(
x
)
∈
R
[
x
]
, with
f
(
x
)=
j
=0
a
j
x
j
, and
a
d
0
is called the
degree of
f
(
x
) over
R
, denoted
by
deg
R
(
f
)
. If no such
d
exists, we write
deg
R
(
f
)=
=0
, then
d
≥
, in which case
f
(
x
)
is the zero polynomial in
R
[
x
]
.If
F
is a field of characteristic zero, then
−∞
deg
(
f
) = deg
F
(
f
)
Q
for any
f
(
x
)
∈
Q
[
x
]
.If
F
has characteristic
p
, and
f
(
x
)
∈
F
p
[
x
]
, then
F
p
(
f
) = deg
F
(
f
)
.
In either case, we write
deg(
f
)
for
deg
F
(
f
)
, without loss of generality, and call
this
the degree of
f
(
x
)
.
deg
With respect to roots of polynomials, the following is important.
Search WWH ::
Custom Search