Proof.
It is sufficient to see that
![$\displaystyle {\Vert f^{\ast} \Vert}_1 \, {\Vert w \Vert}_1 \ \leq \ B \ \ \ \ {\rm and} \ \ \ \ {\Vert g^{\ast} \Vert}_1 \, {\Vert w \Vert}_1 \ \leq \ B$](img341.png) |
(99) |
both hold iff
![$ {\rm normal}({\rm pp}($](img342.png)
w
![$ )) = h$](img343.png)
.
If the conditions hold then
![$\displaystyle {\Vert f^{\ast} w \Vert}_{\infty} \ \leq \ {\Vert f^{\ast} w \Vert}_1 \ \leq \ {\Vert f^{\ast} \Vert}_1 \, {\Vert w \Vert}_1 \ \leq \ B < p/2$](img344.png) |
(100) |
Moreover from the algorithm computations we have
![$\displaystyle {\Vert b \, f \Vert}_{\infty} \ < \ p/2$](img345.png) |
(101) |
and
![$\displaystyle f^{\ast} \, w \ \equiv \ b \, f \mod{p}$](img346.png) |
(102) |
Relations (
100) and (
101) imply
that every coefficient
![$ c$](img325.png)
of
![$ f^{\ast} \, w - b \, f$](img347.png)
satisfies
![$ -p < c < p$](img348.png)
.
Whereas Relation (
102) tells us that
every coefficient
![$ c$](img325.png)
of
![$ f^{\ast} \, w - b \, f$](img347.png)
is a multiple of
![$ p$](img61.png)
.
Therefore we have
![$\displaystyle f^{\ast} \, w \ = \ b \, f$](img349.png) |
(103) |
Similarly we have
![$\displaystyle g^{\ast} \, w \ = \ b \, g$](img350.png) |
(104) |
This implies that
![$ w$](img330.png)
divides
![$ {\gcd}(b \, f, b \, g)$](img351.png)
.
Hence the primitive part of
![$ w$](img330.png)
divides that of
![$ {\gcd}(b \, f, b \, g)$](img351.png)
which is
![$ h$](img92.png)
.
On the other hand
and
have the same degree since
holds and since
does not divide
.
has degree equal or greater to that of
by virtue of
Theorem 3.
Therefore
![$ {\rm pp}(w)$](img352.png)
and
![$ h$](img92.png)
have the same degree and are in fact equal
up to a sign.
Conversely assume that
![$ {\rm normal}({\rm pp}($](img342.png)
w
![$ ))$](img353.png)
is
![$ h$](img92.png)
.
Recall that
![$ w$](img330.png)
and
![$ {\nu}$](img101.png)
have the same degree.
Then the polynomials
![$ {\nu}$](img101.png)
and
![$ h$](img92.png)
have the same degree too.
Hence by virtue of Theorem
3
we have
![$\displaystyle \overline{{\alpha}} \, {\nu} \ = \ \overline{h}$](img354.png) |
(105) |
where
![$ {\alpha} = {\rm lc}(h)$](img244.png)
.
Since
![$ {\alpha}$](img221.png)
divides
![$ b$](img22.png)
let
![$ {\beta}$](img237.png)
be such that
![$ b = {\alpha} \, {\beta}$](img355.png)
.
Hence we have
![$\displaystyle w \ \equiv \ {\beta} \, h \ \equiv \ b \, {\nu} \mod{p}$](img356.png) |
(106) |
Now by construction we have
![$\displaystyle {\Vert w \Vert}_{\infty} \ < \ p/2$](img357.png) |
(107) |
Moreover Corollary
4 states that
![$\displaystyle {\Vert h \Vert}_{\infty} \ \leq \ (n + 1)^{1/2} \, 2^{n} \, {\Vert f \Vert}_{\infty}$](img358.png) |
(108) |
which implies
![$\displaystyle {\Vert {\beta} \, h \Vert}_{\infty} \ \leq \ B \ < \ p/2.$](img359.png) |
(109) |
Relations (
105), (
106) and (
107) imply
![$\displaystyle w \ = \ {\beta} \, h$](img360.png) |
(110) |
Since
![$ h$](img92.png)
divides
![$ f$](img64.png)
and
![$ g$](img98.png)
we deduce from Relation (
109) that
![$ w$](img330.png)
divides
![$ b \, f$](img333.png)
and
![$ b \, g$](img335.png)
.
Hence there exist polynomials
![$ \widehat{f}$](img361.png)
and
![$ \widehat{g}$](img362.png)
such that
![$\displaystyle \widehat{f} \, w \ = \ b \, f \ \ \ \ {\rm and} \ \ \ \ \widehat{g} \, w \ = \ b \, g$](img363.png) |
(111) |
Corollary
4 applied to
![$ (\widehat{f}, w)$](img364.png)
(as factors of
![$ b \, f$](img333.png)
)
and
![$ (\widehat{g},w)$](img365.png)
(as factors of
![$ b \, g$](img335.png)
) shows to
![$\displaystyle {\Vert \widehat{f} \Vert}_1 \, {\Vert w \Vert}_1 \ \leq \ B \ \ \ \ {\rm and} \ \ \ \ {\Vert \widehat{g} \Vert}_1 \, {\Vert w \Vert}_1 \ \leq \ B$](img366.png) |
(112) |
Finally, it follows from the way
![$ f^{\ast}$](img331.png)
and
![$ g^{\ast}$](img334.png)
are computed that we have in fact
![$\displaystyle \widehat{f} \ = \ f^{\ast} \ \ \ \ {\rm and} \ \ \ \ \widehat{g} \ = \ g^{\ast}$](img367.png) |
(113) |
and we proved that Relation (
99)
holds!