Formulas for Linear Symbolic Newton Iteration.

Let $R$ be an Euclidean domain with a regular Euclidean size ${\delta}$ . Let $p \in R$ be a prime element. Let ${\phi} \in R[y]$ and let $a, a_0 \in R$ such that

1. ${\phi}(a) = 0$ ,
2. $a \equiv a_0 \mod{p}$ ,
3. ${\phi}'(a_0) \neq 0 \mod{p}$ .

If $a$ is unknown, but ${\phi}$ and $a_0$ are known then we can compute a $p$ -adic expansion of $a$ as follows. Let $(a_0, a_1, \ldots, a_d)$ be a $p$ -adic expansion of $a$ w.r.t. $p$ . Let $k < d + 1$ be a positive integer. Recall that the element

$$a^{(k)} = a_0 + a_1 p + \cdots a_{k-1} p^{k-1}$$ (1)

is a $p$ -adic approximation of $a$ at order $k$ . Let us denote by ${\Phi}_p$ the canonical homomorphism from $R$ to $R/\langle p \rangle$ . The following formula computes $a_k$ from $a^{(k)}$ :

$${\Phi}_p(\frac{{\phi}(a^{(k)})}{p^k}) = - {\Phi}_p({\phi}'(a_0)) {\Phi}_p(a_k)$$ (2)