Polynomial Newton Iteration
Description
Given a polynomial \(G\left(x, y\right)\), it is known that the polynomial \(f\left(x\right)\) satisfies:
and there exists 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 \(f\left(x\right)\) modulo \(x^{n}\).
Newton's Method
Consider a doubling approach.
First, when \(n=1\), the solution to \(\left[x^{0}\right]G\left(x, f\left(x\right)\right)=0\) needs to be found separately; the assumed \(f_1\) is one such solution.
Suppose we have already obtained the solution \(f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\) modulo \(x^{\left\lceil\frac{n}{2}\right\rceil}\), and we want the solution \(f\left(x\right) = f_n\left(x\right)\) modulo \(x^{n}\).
Perform a Taylor expansion of \(G\left(x, f(x)\right)\) with respect to \(f(x)\) at \(f(x)=f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\):
Since the lowest non-zero term degree of \(f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\) is at least \(\left\lceil\frac{n}{2}\right\rceil\), we have:
Thus:
or equivalently,
Examples
Polynomial Inverse
Let the given function be \(h\left(x\right)\), and define:
Applying Newton's Method yields:
Time complexity:
Polynomial Square Root
Let the given function be \(h\left(x\right)\), and define:
Applying Newton's Method yields:
Time complexity:
Polynomial Exponential Function
Let the given function be \(h\left(x\right)\), and define:
Applying Newton's Method yields:
Time complexity:
Manual Calculation Demonstration
To facilitate understanding, here are a few examples demonstrating the algorithm's process.
Square Root of a Complex Polynomial Modulo a Polynomial
Assume \(h\) is a complex polynomial not divisible by \(x\) (i.e., has a constant term). Find its square root modulo \(x^n\).
We have the equation:
Taylor expand \(G\) to obtain the following expression. Note that this expansion is with respect to \(f\), so the derivatives are partial derivatives with respect to \(f\), and \(x\) is treated as a constant here.
Compute using doubling. Suppose the intermediate results in the doubling process are \(f_0(x), f_1(x), \ldots, f_j(x)\), or more rigorously, \(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 following two conditions:
- The degree of \(f_{j}(x)\) does not exceed \(x^{2^j}\);
- \(f_{j+k}(x)-f_j(x)\equiv 0\pmod{x^{2^j}}\) for all \(k\).
Substituting \(f_{j+1}(x)\) and \(f_j(x)\) into the above expression gives:
Clearly, \(f_{j+1}(x)-f_j(x)\) must be a multiple of \(x^{2^j}\). Thus we obtain:
If \(f_j(x)\) exists, then \(2f_j(x)\) is not divisible by \(x\) (has a constant term), so it must have an inverse modulo \(x^{2^{j+1}}\). Therefore, the sequence \(f_0,f_1\ldots,f_j\) exists if and only if \(f_0\) exists. A complex polynomial \(h(x)\) not divisible by \(x\) always has a square root modulo \(x\), because \(h(x)\) modulo \(x\) is just an ordinary non-zero complex number, which always has two square roots. Thus, this algorithm can be applied to all \(h(x)\) with a constant term.
Take \(h(x)=x+1\) as an example for calculation:
- \(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\) (equal to the negative of the previous one)
It can be verified that both are correct sequences of square root polynomials modulo the respective powers.
Square Root of an Integer Modulo a Prime Power
Newton's iterative algorithm can also be adapted to the case of integers modulo prime powers. Assume \(h\) is an integer not divisible by 3 and is "convenient" (meaning "a solution is guaranteed to exist"; specific conditions will be discussed later). Suppose we want to compute the square root \(f\) of \(h\) modulo \(3^n\). We have the equation:
Taylor expand \(G\):
Compute using doubling. Suppose the intermediate results obtained in the doubling process are \(f_0, f_1, \ldots, f_j\), or more rigorously, \(f_j\) is an integer satisfying \(G(f_j)\equiv 0\pmod{3^{2^j}}\), and for uniqueness, it also satisfies the following two conditions:
- \(0 < f_{j} < 3^{2^j}\);
- \(f_{j+k}-f_j\equiv 0\pmod{3^{2^j}}\) for all \(k\).
Substituting \(f_{j+1}\) and \(f_j\) into the above expression gives:
Clearly, \(f_{j+1}-f_j\) must be a multiple of \(3^{2^j}\). Thus we obtain:
If \(f_j\) exists, then \(2f_j\) is not divisible by \(3\), so it must have an inverse modulo \(3^{2^{j+1}}\). Therefore, 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 modulo \(3\), or has two. Thus, \(h\) having a square root modulo \(3\) is the only condition for the algorithm to run.
Here is an actual calculation 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\) (equal to the negative of the previous one)
It can be verified that both are correct sequences of square roots modulo the respective powers.
Algebraic Proof
This section extends the previous discussion, using the language of abstract algebra to prove that as long as \(f\) satisfies the initial solution conditions, Newton's method yields a solution for all \(n\), and all solutions can be obtained.
Proof of Existence of Solutions
Lemma 1
Let \(R\) be an integral domain with a polynomial or formal power series \(f(X) = \sum_{i\geq 0}a_iX^i\) and \(r,p\in R\) such that \(f(r)\in Rp\) (i.e., \(r\) is a root of \(f(X)\) modulo \(p\)) and \(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 all \(s\in R\),
so
Since \(f(r)\in Rp\) and \(f'(r)\) is invertible, take \(sp = -\dfrac{f(r)}{f'(r)}\), where \(\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\) such that \(af'(r) = bp+1\) and \(f(r)=cp\), then \(\left(a^2f'(r)-2\right)f'(r) = b^2p^2+1\), so we can take \(s=c(2-a^2f'(r))\).
For the polynomial ring \(k[X]\) over a field \(k\), given \(G(X, Y)\in k[X, Y]\) and \(f_n\in k[X]\) such that \(G(X, f_n(X))\in k[X]X^n\), applying Lemma 1 yields
The initial condition for the doubling only requires \(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 non-zero constant term, and because \(X\left| \dfrac{G(X, f_n(X))}{\frac{\partial G}{\partial Y}(X, f_n(X))} \right.\), for all \(n\), \(\dfrac{\partial G}{\partial Y}(X, f_n)\) is always invertible modulo \(X^n\), satisfying the condition for the next iteration.
Proof of Obtaining All Solutions
Lemma 2
If \(R\) is a UFD, and \(f,r,p\) are defined as in Lemma 1, then the value \(r-\dfrac{f(r)}{f'(r)}\) given by Lemma 1 is the unique value modulo \(p^{2}\) satisfying the following two conditions:
- \(f(x)\in Rp^{2}\)
- \(x-r\in Rp\)
i.e.,
Proof
Let \(s = -\dfrac{f(r)}{f'(r)p}\) and \(u = r+sp\). Lemma 1 guarantees that \(u\) satisfies both conditions, and \(f(r) + f'(r)sp \in Rp^{2}\). Let \(v\) be a value satisfying the above conditions, 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 guarantees obtaining all solutions modulo \(X^{2^n}\). Suppose \(G(X, h)\equiv 0\pmod {X^{2^n}}\), then let \(h_{2^i} := h\pmod {X^{2^i}}\), take \(f_1 = h_1\), and apply Newton's method. By Lemma 2, we have \(f_{2^i} \equiv h_{2^i}\pmod {X^{2^i}}\), so necessarily \(f_{2^n} = h\).
The above argument 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 non-trivial. See the following example.
Example where Newton's method fails and the number of solutions increases with degree
Modulo \(X\), the square root of \(X^2\) is only \(0\), but modulo \(X^4\), the square roots of \(X^2\) include \(X, -X, X^3+X, \ldots\).
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用