Cryptography Reference
In-Depth Information
=
=
=
Proof
The case
f
0 is trivial, just set
q
r
0. Thus we will assume in
=
(
)<
(
)
=
=
the sequel that
f
0. Now, if deg
f
deg
g
, then we set
q
0 and
r
f
.
Therefore we may also assume that deg
. The proof of the existence of
q
and
r
proceeds by induction on the degree of
f
.Ifdeg
(
g
)
≤
deg
(
f
)
(
f
)
=
0 then deg
(
g
)
=
0
too, so that both
f
and
g
are nonzero constant polynomials and hence units in
k
[
x
]
,
fg
−
1
and
r
and we set
q
=
=
0.
Suppose now that deg
(
f
)
=
n
>
0, where
n
≥
m
=
deg
(
g
)
, and let
n
m
a
i
x
i
b
i
x
i
=
,
=
.
f
and
g
i
=
0
i
=
0
a
n
b
−
1
x
n
−
m
g
and since deg
Then we set
f
1
=
f
−
(
f
1
)<
deg
(
f
)
, we may use the
m
induction hypothesis to conclude that there are polynomials
q
1
,
r
∈
k
[
x
]
such that
f
1
=
+
(
)<
(
)
q
1
g
r
, with deg
r
deg
g
. Then, replacing this value of
f
1
in the previous
equation we obtain:
a
n
b
−
m
x
n
−
m
f
=
(
+
q
1
)
g
+
r
,
a
n
b
−
1
x
n
−
m
so that
q
q
1
and
r
satisfy the assertion of the theorem.
To prove uniqueness, let
f
=
+
m
gq
+
r
, with max
r
)
}
<
=
gq
+
r
=
{
deg
(
r
),
deg
(
q
)
=
r
−
q
)
=
r
)
≤
deg
(
g
)
. Then
g
(
q
−
r
and so deg
(
g
)
+
deg
(
q
−
deg
(
r
−
r
)
}
<
max
{
deg
(
r
),
deg
(
deg
(
g
)
(by Proposition 2.10 and the hypothesis). This
q
)
=−∞
q
. Thus
inequality can only hold if deg
(
q
−
, i.e., we have that
q
=
r
−
q
)
=
0 and we also have
r
=
r
=
g
(
q
−
g
0
=
r
.
The preceding proof gives an algorithm to perform the division of polynomials:
Algorithm 2.6. Polynomial division
.
Input
: Polynomials
f
,
g
∈
k
[
x
]
, such that
g
=
0.
Output
:
q
,
r
∈
k
[
x
]
such that
f
=
gq
+
r
and deg
(
r
)<
deg
(
g
)
.
1.
Set
r
0.
2.
Compute
the quotient and the remainder:
while
deg
(
r
)
≥
deg
(
g
)
do
a
:= leading coefficient of
r
b
:= leading coefficient of
g
h
:=
ab
−
1
x
deg
(
r
)
−
deg
(
g
)
r
:=
r
−
hg
q
:=
q
+
h
end do
3.
return
:
q
,
r
.
:=
f
and
q
:=
The remainder of dividing
f
by
g
is denoted by
f
mod
g
. In Maple, division
of polynomials is implemented in the functions
Rem
(we already used this function
when we defined the multiplication
mult4
) and
Quo
. These functions, when used
