Exercise 2.

The algorithm recalled above computes the inverse of $f \in R[x]$ modulo $x^{\ell}$ . Using Newton iteration step

$$g_{i+1} \ = \ g_i - \frac{{\phi}(g_i)}{{\phi}'(g_{i})}$$ (1)

derive an algorithm which, given $f \in R[x]$ and ${\ell} \in {\mbox{${\mathbb{N}}$}}$ , computes $g \in R[x]$ such that $f g^2 \equiv 1 \mod{ \ x^{\ell}}$ holds. Then, prove that the algorithm is correct.

Answer 2