Cryptography Reference
In-Depth Information
> Gcd(f, g) mod 2;
1
We see that these polynomials are relatively prime. We use the extended Euclidean
algorithm to compute
s
,
t
∈
k
[
x
]
such that 1
=
sf
+
tg
:
> Gcdex(f, g, x, 's', 't') mod 2;
s, t;
1
xˆ6+xˆ5+xˆ4+xˆ3+xˆ2+x+1,xˆ11 + xˆ10 + xˆ9 + xˆ6 + xˆ4 + xˆ3 + xˆ2 + x
x
6
x
5
x
4
x
3
x
2
x
11
x
10
x
9
x
6
We see that,
s
=
+
+
+
+
+
x
+
1,
t
=
+
+
+
+
x
4
x
3
x
2
+
+
+
x
in this case. We may check that they satisfy 1
=
sf
+
tg
:
> Expand(s*f+t*g) mod 2;
1
An element
α
∈
k
is said to be a
zero
of
f
∈
k
[
x
]
whenever
f
(α)
=
0 (where,
as usual,
f
(α)
denotes the element of
k
obtained by substituting
x
=
α
into the
polynomial and carrying out the field operations, so that
α
is a root of the equation
is a root of
f
). There is a simple test to determine
whether an element of
k
is a zero of
f
in terms of divisibility:
f
(
x
)
=
0 and we also say that
α
Theorem 2.21
Let f
∈
k
[
x
]
and
α
∈
k. Then
α
is a zero of f if and only if
(
x
−
α)
|
f.
Proof
We divide
f
by
x
−
α
and we have
f
=
(
x
−
α)
q
+
r
. Then
f
(α)
=
r
and
(α)
=
α
=
(
−
α)
|
hence
f
0 (i.e.,
is a zero of
f
) if and only if
r
0 (i.e.,
x
f
).
Example 2.22
Since 1 is a zero of
x
2
and also of
x
3
+
1
∈ Z
2
[
x
]
+
1
∈ Z
2
[
x
]
,
we see that
x
+
1
∈ Z
2
[
x
]
divides both polynomials. Indeed, one easily checks that
x
2
2
and also that
x
3
x
2
+
1
=
(
x
+
1
)
∈ Z
2
[
x
]
+
1
=
(
x
+
1
)(
+
x
+
1
)
∈ Z
2
[
x
]
(note that no minus signs appear here because
−
1
=
1in
Z
2
). In fact, 1 is a zero
of the polynomial
x
n
0 and it is easily seen that
x
n
+
1
∈ Z
2
[
x
]
for all
n
>
+
1
=
x
n
−
1
x
n
−
2
(
x
+
1
)(
+
+···+
1
)
∈ Z
2
[
x
]
.
Corollary 2.4
A nonzero polynomial f
∈
k
[
x
]
has at most
deg
(
f
)
zeros.
Proof
We use induction on
n
=
deg
(
f
)
.If
n
=
0 then
f
is a nonzero element of
k
and hence
f
has no zeros. Suppose now that
n
>
0. If
f
has no zeros then the
α
assertionistruesowemayassumethat
f
has a zero
. By Theorem 2.21 we have
=
(
−
α)
(
)
=
−
that
f
x
q
where deg
q
n
1. The induction hypothesis then implies
that
q
has at most
n
−
1 zeros from which it follows that
f
has at most
n
zeros.
t
g
,
If
α
is a zero of
f
∈
k
[
x
]
, then the maximum value of
t
such that
f
=
(
x
−
α)
with
g
∈
k
[
x
]
, is called the
multiplicity
of
α
in
f
and we often say that
α
is a
multiple
zero
(or a
multiple root
) when
t
1. It is not difficult to see that Corollary 2.4 is
also valid if one counts multiplicities, i.e., the sum of the multiplicities of the zeros
of a polynomial cannot exceed its degree.
>
