「Learning Notes」Newton's Method

本文会随着笔者的水平提升持续更新.
若发现文中有叙述不严谨之处,欢迎指出。

Description

给定多项式 g(x) ,已知有 f(x) 满足:

g\left(f(x)\right) \equiv 0 \pmod{x^{n}}

求出模 x^{n} 意义下的 f(x)

Newton's Method

考虑倍增.

首先当 n = 1 时, \left[x^{0}\right] g\left(f(x)\right) = 0 的解需要单独求出。

假设现在已经得到了模 x^{\left\lceil\frac{n}{2}\right\rceil} 意义下的解 f_{0}(x) ,要求模 x^{n} 意义下的解 f(x)
g\left(f(x)\right) f_{0}(x) 处进行泰勒展开,有:

\sum_{i = 0}^{+\infty} \frac{g^{(i)}\left(f_{0}(x)\right)}{i!} \left(f(x) - f_{0}(x)\right)^{i} \equiv 0 \pmod{x^{n}}

因为 f(x) - f_{0}(x) 的最低非零项次数最低为 \left\lceil\frac{n}{2}\right\rceil ,故有:

\forall 2 \le i : \left(f(x) - f_{0}(x)\right)^{i} \equiv 0 \pmod{x^{n}}

则:

\sum_{i = 0}^{+\infty} \frac{g^{(i)}\left(f_{0}(x)\right)}{i!} \left(f(x) - f_{0}(x)\right)^{i} \equiv g\left(f_{0}(x)\right) + g'\left(f_{0}(x)\right) \left(f(x) - f_{0}(x)\right) \equiv 0 \pmod{x^{n}}

f(x) \equiv f_{0}(x) - \frac{g\left(f_{0}(x)\right)}{g'\left(f_{0}(x)\right)} \pmod{x^{n}}

Examples

多项式求逆

设给定函数为 h(x) ,有方程:

g\left(f(x)\right) = \frac{1}{f(x)}-h(x)\equiv 0\pmod{x^{n}}

应用 Newton's Method 可得:

\begin{aligned} f(x)&\equiv f_{0}(x)-\frac{\frac{1}{f_{0}(x)}-h(x)}{-\frac{1}{f_{0}^{2}(x)}}&\pmod{x^{n}}\\ &\equiv 2f_{0}(x)-f_{0}^{2}(x)h(x)&\pmod{x^{n}} \end{aligned}

时间复杂度

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

多项式开方

设给定函数为 h(x) ,有方程:

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

应用 Newton's Method 可得:

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

时间复杂度

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

多项式 exp

设给定函数为 h(x) ,有方程:

g\left(f(x)\right) = \ln{f(x)}-h(x)\pmod{x^{n}}

应用 Newton's Method 可得:

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

时间复杂度

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