Cryptography Reference
In-Depth Information
Definition A.33
(
Discriminant of Polynomials)
Let
f
(
x
)=
a
j
=1
(
x
−
α
j
)
∈
F
[
x
]
,
deg(
f
)=
n>
1
,
a
∈
F
a field in
C
, where
α
j
∈
C
are all the roots of
f
(
x
)=0
for
j
=1
,
2
,...,n
. Then the
discriminant
of
f
is given by
disc(
f
)=
a
2
n
−
2
α
i
)
2
.
(
α
j
−
1
≤
i<j
≤
n
From Definition A.33, we see that
f
has a multiple root in
C
(namely, for
some
i
=
j
we have
α
i
=
α
j
, also called a
repeated root
) if and only if disc(
f
)=0.
Definition A.34
(
Division of Polynomials
)
We say that a
polynomial
g
(
x
)
∈
R
[
x
]divides
f
(
x
)
∈
R
[
x
]
, if there exists
an
h
(
x
)
∈
R
[
x
]
such that
f
(
x
)=
g
(
x
)
h
(
x
)
. We also say that
g
(
x
)
is a
factor
of
f
(
x
)
.
Definition A.35 Irreducible Polynomials over Rings
A polynomial
f
(
x
)
R
[
x
]
is called
irreducible (
over
R
)
,if
f
(
x
)
is not a unit
in
R
and any factorization
f
(
x
)=
g
(
x
)
h
(
x
)
, with
g
(
x
)
,h
(
x
)
∈
R
[
x
]
satisfies the
property that one of
g
(
x
)
or
h
(
x
)
is in
R
, called a
constant polynomial
. In other
words,
f
(
x
)
cannot be the product of two nonconstant polynomials. If
f
(
x
)
is
not irreducible, then it is said to be reducible.
∈
Remark A.1
Note that it is possible that a reducible polynomial
f
(
x
)
could be
a product of two polynomials of the
same degree
as that of
f
. For instance,
−
x
)=(2
x
+ 1)(3
x
+1)
in
R
=
Z
Z
f
(
x
)=(1
/
6
.
The following will be needed in our discussions on secret sharing in Section
5.5, for instance.
Theorem A.20
(
The Lagrange Interpolation Formula
)
Let
F
be a field,
and let
a
j
for
j
=0
,
1
,
2
,...,n
be distinct elements of
F
. f
c
j
for
j
=
0
,
1
,
2
,...,n
are any elements of
F
, then
n
(
x
−
a
0
)
···
(
x
−
a
j
−
1
)(
x
−
a
j
+1
)
···
(
x
−
a
n
)
f
(
x
)=
a
n
)
c
j
(
a
j
−
a
0
)
···
(
a
j
−
a
j
−
1
)(
a
j
−
a
j
+1
)
···
(
a
j
−
j
=0
is the unique polynomial in
F
[
x
]
such that
f
(
a
j
)=
c
j
for all
j
=0
,
1
,...,n
.
Search WWH ::
Custom Search