Proof.
Since
![$ {\phi}'(g)$](img183.png)
is invertible modulo
![$ p$](img5.png)
then
![$ {\phi}'(g)$](img183.png)
is invertible modulo
![$ p^{2}$](img191.png)
.
(This is easy to check: Exercise!)
Hence Relation
31 makes sense.
In fact, Algorithm
![[*]](crossref.png)
computes
![$ {{\phi}'(g)}^{-1} \mod{ p^{2}}$](img192.png)
given
![$ {{\phi}'(g)}^{-1} \mod{ p }$](img193.png)
.
Since
divides
, the following congruence holds
![$\displaystyle h \ {\equiv} \ g - {\phi}(g) \, {{\phi}'(g)}^{-1} \mod{ p}$](img194.png) |
(32) |
Since
![$ {\phi}(g) \ {\equiv} \ 0 \mod{p}$](img195.png)
, this leads to
![$\displaystyle h \ {\equiv} \ g \mod{ p}$](img196.png) |
(33) |
and we have proved the second claim.
Let us prove the first one.
Using the Taylor expansion of
![$ {\phi}$](img71.png)
at
![$ h$](img197.png)
and the fact that
![$ p^2$](img190.png)
divides
![$ (h -g)^2$](img198.png)
we obtain
![\begin{displaymath}\begin{array}{rcl} {\phi}(h) & {\equiv} & {\phi}(g) + {{\phi}...
...g)}^{-1} \mod{ p^2} \\ & {\equiv} & 0 \mod{ p^2} \\ \end{array}\end{displaymath}](img199.png) |
(34) |
proving the first claim.
Finally, observe that
![$ h \ {\equiv} \ g \mod{ p}$](img188.png)
implies
![$ {\phi}'(h) \ {\equiv} \ {\phi}'(g) \mod{ p}$](img200.png)
.
Indeed
![$ {\phi}'$](img201.png)
is a polynomial in
![$ R[x]$](img202.png)
.
Therefore,
![$ {\phi}'(h)$](img189.png)
is invertible modulo
![$ p$](img5.png)
,
since
![$ {\phi}'(g)$](img183.png)
is invertible modulo
![$ p$](img5.png)
, by hypothesis.
Proof.
Let
![$ g_r \ {\equiv} \ g_{r-1} - {\phi}(g_{r-1}) s_{r-1} \mod{p^{2^r}}$](img205.png)
.
Then we have
![$\displaystyle g \ {\equiv} \ g_r \ \mod{ p^{\ell}}$](img206.png) |
(36) |
In other words
![$ g_r$](img207.png)
is a
solution of higher precision.
Then proving the theorem turns into proving the invariants for
-
,
-
,
- if
then
.
The case
![$ i = 0$](img213.png)
is clear and we assume that
![$ i > 0$](img214.png)
holds.
Then by induction hypothesis
![$ p^{2^{i-1}}$](img215.png)
divides
![$ {\phi}(g_{i-1})$](img216.png)
and
![$ s_{i-1} - {{\phi}'(g_{i-1})}^{-1}$](img217.png)
.
Then
![$ p^{2^i}$](img218.png)
divides their product, that is
![$\displaystyle {\phi}(g_{i-1}) s_{i-1} \ {\equiv} \ {\phi}(g_{i-1}) {{\phi}'(g_{i-1})}^{-1} \ \mod{ p^{2^i}}.$](img219.png) |
(37) |
Now we calculate
![\begin{displaymath}\begin{array}{rcl} g_i & {\equiv} & g_{i-1} - {\phi}(g_{i-1})...
...g_{i-1}) {{\phi}'(g_{i-1})}^{-1} \ \mod{p^{2^i}} \\ \end{array}\end{displaymath}](img220.png) |
(38) |
Now applying Proposition
8
with
![$ g = g_{i-1}$](img221.png)
,
![$ h = g_i$](img222.png)
and
![$ m = p^{2^{i-1}}$](img223.png)
we obtain the first two invariants.
In addition, this leads to
![$\displaystyle g_i \ \equiv \ g_{i-1} \ \mod{ p^{2^{i-1}} }$](img224.png) |
(39) |
for
![$ i < r$](img211.png)
.
This implies
![$\displaystyle {{\phi}'(g_i)}^{-1} \ \equiv \ {{\phi}'(g_{i-1})}^{-1} \ \equiv \ s_{i-1} \ \mod{ p^{2^{i-1}} }$](img225.png) |
(40) |
Now,
![$ s_i$](img226.png)
is obtained by one Newton step for inversion
(see Algorithm
![[*]](crossref.png)
).
Therefore the third invariant follows.