Polynomial Newton iteration

Description

Given a polynomial $G\left(x, y\right)$, suppose the polynomial $f\left(x\right)$ satisfies:

$$G\left(x, f\left(x\right)\right)\equiv 0\pmod{x^{n}}$$

and there is a value $f_1$ such that $G\left(x, y\right)$ satisfies the following conditions:

• $G(0, f_1) = 0$；
• $\dfrac{\partial G}{\partial y}(0, f_1) \neq 0$．

Find, modulo $x^{n}$, $f\left(x\right)$.

Newton's Method

Consider doubling the precision.

First, when $n=1$, the solution to $\left[x^{0}\right]G\left(x, f\left(x\right)\right)=0$ must be found separately; the $f_1$ in the assumption is one such solution.

Suppose we have obtained, modulo $x^{\left\lceil\frac{n}{2}\right\rceil}$, a solution $f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)$, and want, modulo $x^{n}$, a solution $f\left(x\right) = f_n\left(x\right)$.

Expand $G\left(x, f(x)\right)$ in a Taylor series in $f(x)$ around $f(x)=f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)$:

$$\sum_{i=0}^{+\infty}\frac{\frac{\partial^i G}{\partial y^i}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}}$$

Because the lowest possible degree of a nonzero term in $f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)$ is $\left\lceil\frac{n}{2}\right\rceil$, we have:

$$\forall 2\leqslant i:\left(f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}}$$

Thus:

$$\begin{aligned} \sum_{i=0}^{+\infty}\frac{\frac{\partial^i G}{\partial y^i}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)^{i}&\equiv G\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)+\frac{\partial G}{\partial y}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)\left[f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right]\\ &\equiv 0\pmod{x^{n}} \end{aligned}$$ $$f_n\left(x\right)\equiv f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)-\frac{G\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}{\frac{\partial G}{\partial y}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}\pmod{x^{n}}$$

Or, equivalently,

$$f_{2n}\left(x\right)\equiv f_n\left(x\right)-\frac{G\left(x, f_n\left(x\right)\right)}{\frac{\partial G}{\partial y}\left(x, f_n\left(x\right)\right)}\pmod{x^{2n}}$$

Examples

Polynomial inversion

Let the given function be $h\left(x\right)$, with:

$$G\left(x, y\right)=\frac{1}{y}-h\left(x\right)$$

Applying Newton's Method gives:

$$\begin{aligned} f_{2n}\left(x\right)&\equiv f_{n}\left(x\right)-\frac{1/f_{n}\left(x\right)-h\left(x\right)}{-1/f_{n}^{2}\left(x\right)}&\pmod{x^{2n}}\\ &\equiv 2f_{n}\left(x\right)-f_{n}^{2}\left(x\right)h\left(x\right)&\pmod{x^{2n}} \end{aligned}$$

The time complexity is

$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)$$

Polynomial square root

Let the given function be $h\left(x\right)$, with:

$$G\left(x, y\right)=y^{2}-h\left(x\right)\equiv 0$$

Applying Newton's Method gives:

$$\begin{aligned} f_{2n}\left(x\right)&\equiv f_{n}\left(x\right)-\frac{f_{n}^{2}\left(x\right)-h\left(x\right)}{2f_{n}\left(x\right)}&\pmod{x^{2n}}\\ &\equiv\frac{f_{n}^{2}\left(x\right)+h\left(x\right)}{2f_{n}\left(x\right)}&\pmod{x^{2n}} \end{aligned}$$

The time complexity is

$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)$$

Polynomial exponential function

Let the given function be $h\left(x\right)$, with:

$$G\left(x, y\right)=\ln{y}-h\left(x\right)$$

Applying Newton's Method gives:

$$\begin{aligned} f_{2n}\left(x\right)&\equiv f_{n}\left(x\right)-\frac{\ln{f_{n}\left(x\right)}-h\left(x\right)}{1/f_{n}\left(x\right)}&\pmod{x^{2n}}\\ &\equiv f_{n}\left(x\right)\left(1-\ln{f_{n}\left(x\right)+h\left(x\right)}\right)&\pmod{x^{2n}} \end{aligned}$$

The time complexity is

$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)$$

Worked examples

For clarity, we give several examples to demonstrate the algorithm.

Square roots of complex polynomials modulo a polynomial

Suppose $h$ is a complex polynomial not divisible by $x$ (that is, it has a nonzero constant term). Find its square root modulo $x^n$.

We have the equation:

$$G\left(f(x)\right) = f^2(x)-h(x) \equiv 0\pmod{x^{n}}$$

Taylor expansion of $G$ gives the following. Note that this expansion is with respect to $f$, so all derivatives are partial derivatives with respect to $f$; $x$ is treated as a constant here.

$$G(f(x)) = \sum_{i=0}^{+\infty}\frac{G^{\left(i\right)}\left(f_{0}(x)\right)}{i!}\left(f(x)-f_{0}(x)\right)^{i} = G(f_0(x)) + 2f_0(x)(f(x)-f_0(x)) + (f(x)-f_0(x))^2$$

Use doubling. Suppose the intermediate results in the doubling process are $f_0(x), f_1(x), \ldots, f_j(x)$; more precisely, $f_j(x)$ is a complex polynomial satisfying $G(f_j(x))\equiv 0\pmod{x^{2^j}}$, and for uniqueness it also satisfies:

• The degree of $f_{j}(x)$ is no greater than $x^{2^j}$;
• $f_{j+k}(x)-f_j(x)\equiv 0\pmod{x^{2^j}}$ for every $k$.

Substituting $f_{j+1}(x)$ and $f_j(x)$ into the equation above gives:

$$G(f_{j+1}(x)) = G(f_j(x)) + 2f_j(f_{j+1}(x)-f_j(x)) + (f_{j+1}(x)-f_{j}(x))^2 \equiv 0 \pmod{x^{2^{j+1}}}$$

Clearly, $f_{j+1}(x)-f_j(x)$ must be a multiple of $x^{2^j}$. Therefore,

$$f_{j+1}(x) \equiv f_j(x) - \frac{f_j^2(x)-h(x)}{2f_j(x)} \equiv \frac{f_j(x)^2 + h(x)}{2f_j(x)} \pmod{x^{2^{j+1}}}$$

If $f_j(x)$ exists, then $2f_j(x)$ is not divisible by $x$ (it has a nonzero constant term), so it has an inverse modulo $x^{2^{j+1}}$. Thus the sequence $f_0,f_1\ldots,f_j$ exists if and only if $f_0$ exists. A complex polynomial not divisible by $x$, namely $h(x)$, always has a square root modulo $x$, because reducing $h(x)$ modulo $x$ gives an ordinary nonzero complex number, which always has two square roots. Therefore this algorithm works for every $h(x)$ with a nonzero constant term.

For example, take $h(x)=x+1$:

• $f_0(x)=1$,$f_1(x)=\dfrac{1^2+x+1}{2\times 1}\mod x^2 = \dfrac{1}{2}x+1$,$f_2(x)=\dfrac{\left(\dfrac{1}{2}x+1\right)^2+x+1}{2\times \left(\dfrac{1}{2}x+1\right)}\mod x^4 = \dfrac{1}{16}x^3-\dfrac{1}{8}x^2+\dfrac{1}{2}x+1$,$\ldots$
• $f_0(x)=-1$,$f_1(x)=\dfrac{(-1)^2+x+1}{2\times (-1)}\mod x^2 = -\dfrac{1}{2}x-1$,$\ldots$ (the negative of the preceding one)

It can be verified that both are valid sequences of polynomial square roots modulo the modulus.

Square roots of integers modulo prime powers

Newton iteration also extends to the case of integers modulo powers of a prime. Suppose $h$ is a “convenient” integer not divisible by 3 (“convenient” means that a solution is guaranteed to exist; the precise condition is given below). Suppose the square root of $h$ modulo $3^n$ to be computed is $f$. We have:

$$G\left(f\right) = f^2-h \equiv 0\pmod{3^{n}}$$

Taylor expansion of $G$ gives:

$$G(f) = \sum_{i=0}^{+\infty}\frac{G^{\left(i\right)}\left(f_{0}\right)}{i!}\left(f-f_{0}\right)^{i} = G(f_0) + 2f_0(f-f_0) + (f-f_0)^2$$

Use doubling. Suppose the intermediate results obtained during doubling are $f_0, f_1, \ldots, f_j$; more rigorously, $f_j$ is an integer satisfying $G(f_j)\equiv 0\pmod{3^{2^j}}$, and for uniqueness it also satisfies:

• $0 < f_{j} < 3^{2^j}$;
• $f_{j+k}-f_j\equiv 0\pmod{3^{2^j}}$ for every $k$.

Substituting $f_{j+1}$ and $f_j$ into the equation above gives:

$$G(f_{j+1}) = G(f_j) + 2f_j(f_{j+1}-f_j) + (f_{j+1}-f_{j})^2 \equiv 0 \pmod{3^{2^{j+1}}}$$

Clearly, $f_{j+1}-f_j$ must be a multiple of $3^{2^j}$. Therefore,

$$f_{j+1} \equiv f_j - \frac{f_j^2-h}{2f_j} \equiv \frac{f_j^2 + h}{2f_j} \pmod{3^{2^{j+1}}}$$

If $f_j$ exists, then $2f_j$ is not divisible by $3$, so it has an inverse modulo $3^{2^{j+1}}$. Thus the sequence $f_0,f_1\ldots,f_j$ exists if and only if $f_0$ exists. An integer $h$ not divisible by 3 either has no square root or has two modulo $3$. Therefore, $h$ having a square root modulo $3$ is the only condition needed for the algorithm to run.

Here is a worked example with $h=46$.

• $f_0=1$,$f_1=\dfrac{1^2+46}{2\times 1}\mod 9 = 1$,$f_2=\dfrac{1^2+46}{2\times 1}\mod 81 = 64$,$f_3=\dfrac{64^2+46}{2\times 64}\mod 6561 = 955$,$\ldots$
• $f_0=2$,$f_1=\dfrac{2^2+46}{2\times 2}\mod 9 = 8$,$f_2=\dfrac{8^2+46}{2\times 8}\mod 81 = 17$,$f_3=\dfrac{17^2+46}{2\times 17}\mod 6561 = 5606$,$\ldots$ (the negative of the preceding one)

It can be verified that both are valid sequences of square roots modulo prime powers.

Algebraic proof

This section develops the preceding discussion further. Using the language of abstract algebra, we prove that as long as $f$ satisfies the initial-solution condition, Newton's method produces a solution for every $n$ and can produce all solutions.

Proof of existence

Lemma 1

Let the integral domain $R$ contain a polynomial or formal power series $f(X) = \sum_{i\geq 0}a_iX^i$, and let $r,p\in R$ satisfy $f(r)\in Rp$ (that is, $r$ is a root of $f(X)$ modulo $p$) while $f'(r)\in R$ is invertible modulo $p$. Here $f'(X) := \sum_{i\geq 0}(i+1)a_{i+1}X^i$ is the formal derivative of $f(X)$. Then $f\left(r-\dfrac{f(r)}{f'(r)}\right) \equiv 0\pmod {p^2}$.

Proof

For every $s\in R$,

$$\begin{aligned} f(r+sp) &= \sum_{i\geq 0}a_i(r+sp)^i \\ &= \sum_{i\geq 0}a_ir^i + sp\sum_{i\geq 1}ia_ir^{i-1} + s^2p^2\left(\ldots\right) \\ &= f(r) + spf'(r) + s^2p^2\left(\frac{f''(r)}{2!} + \cdots\right), \end{aligned}$$

Therefore

$$f(r+sp) \in Rp^2 \iff f(r)+f'(r)sp \in Rp^2$$

Since $f(r)\in Rp$ and $f'(r)$ is invertible, it suffices to take $sp = -\dfrac{f(r)}{f'(r)}$; here $\dfrac{1}{f'(r)}$ is the inverse modulo $p^2$. Because $f'(r)$ is invertible modulo $p$, it must also have an inverse modulo $p^2$: let $a,b,c\in R$ satisfy $af'(r) = bp+1$ and $f(r)=cp$. Then $\left(a^2f'(r)-2\right)f'(r) = b^2p^2+1$, so we may take $s=c(2-a^2f'(r))$.

For a field $k$, consider its polynomial ring $k[X]$. Suppose $G(X, Y)\in k[X, Y]$ and $f_n\in k[X]$ satisfy $G(X, f_n(X))\in k[X]X^n$. Applying Lemma 1 gives

$$G\left(X, f_n(X) - \frac{G(X, f_n(X))}{\frac{\partial G}{\partial Y}(X, f_n(X))} \right)\equiv 0 \pmod {X^{2n}}$$

For doubling, the initial conditions only require an $f_1\in k$ such that $G(X, f_1)\equiv 0\pmod X$ and $\dfrac{\partial G}{\partial Y}(X, f_1)\not\equiv 0\pmod X$. The latter condition ensures that $\dfrac{\partial G}{\partial Y}$ has a nonzero constant term. Since $X\left| \dfrac{G(X, f_n(X))}{\frac{\partial G}{\partial Y}(X, f_n(X))} \right.$, for every $n$, $\dfrac{\partial G}{\partial Y}(X, f_n)$ is always invertible modulo $X^n$, so the condition for the next iteration is satisfied.

Proof that all solutions are obtained

Lemma 2

If $R$ is a UFD, with $f,r,p$ defined as in Lemma 1, then the value $r-\dfrac{f(r)}{f'(r)}$ given by Lemma 1 is, modulo $p^{2}$, the unique value of $x$ satisfying:

• $f(x)\in Rp^{2}$
• $x-r\in Rp$

In other words,

$$\forall x\in R,\qquad p^2\mid f(x)\wedge p\mid (x-r) \implies x\equiv r-\dfrac{f(r)}{f'(r)} \pmod {p^2}$$

Proof

Let $s = -\dfrac{f(r)}{f'(r)p}$ and $u = r+sp$. Lemma 1 guarantees that $u$ satisfies both conditions, and that $f(r) + f'(r)sp \in Rp^{2}$. If $v$ is a value satisfying the conditions above, then $v = r+tp$ and $f(r) + f'(r)tp \in Rp^{2}$. Hence $f'(r)(t-s)p\in Rp^{2}$ and $v-u\in Rp^{2}$.

Newton's method can obtain all solutions modulo $X^{2^n}$. Suppose $G(X, h)\equiv 0\pmod {X^{2^n}}$. Set $h_{2^i} := h\pmod {X^{2^i}}$, take $f_1 = h_1$, and apply Newton's method. Lemma 2 gives $f_{2^i} \equiv h_{2^i}\pmod {X^{2^i}}$, so necessarily $f_{2^n} = h$.

The argument above also shows that when $\dfrac{\partial G}{\partial y}(0, y)$ is always invertible, the number of solutions to $G(X, f)\equiv 0\pmod {X^n}$ equals the number of solutions to $G(0, f)\equiv 0\pmod X$. This conclusion is not trivial; consider the following example.

An example where the number of solutions increases with the degree when Newton's method is invalid

Modulo $X$, the only square root of $X^2$ is $0$, but modulo $X^4$, the square roots of $X^2$ include $X, -X, X^3+X, \ldots$.