多项式牛顿迭代

描述

给定多项式 ，已知有 满足：

求出模 意义下的 。

Newton's Method

考虑倍增。

首先当 时， 的解需要单独求出。

假设现在已经得到了模 意义下的解 ，要求模 意义下的解 。

将 在 处进行泰勒展开，有：

因为 的最低非零项次数最低为 ，故有：

则：

例题

多项式求逆

设给定函数为 ，有方程：

应用 Newton's Method 可得：

时间复杂度

多项式开方

设给定函数为 ，有方程：

应用 Newton's Method 可得：

时间复杂度

多项式 exp

设给定函数为 ，有方程：

应用 Newton's Method 可得：

时间复杂度