跳转至

# 多项式牛顿迭代

## 描述

给定多项式 𝐺(𝑥,𝑦)G(x,y)，已知多项式 𝑓(𝑥)f(x) 满足：

𝐺(𝑥,𝑓(𝑥))≡0(m o d 𝑥 𝑛)G(x,f(x))≡0(mod x n)

且存在数值 𝑓 1 f 1 使 𝐺(𝑥,𝑦)G(x,y) 满足以下条件：

- 𝐺(0,𝑓 1) =0 G(0,f 1)=0；
- 𝜕𝐺𝜕𝑦(0,𝑓 1) ≠0∂G∂y(0,f 1)≠0．

求出模 𝑥 𝑛 x n 意义下的 𝑓(𝑥)f(x)．

## Newton's Method

考虑倍增．

首先当 𝑛 =1 n=1 时，[𝑥 0]𝐺(𝑥,𝑓(𝑥)) =0[x 0]G(x,f(x))=0 的解需要单独求出，假设中的 𝑓 1 f 1 即为一个解．

假设现在已经得到了模 𝑥⌈𝑛 2⌉x⌈n 2⌉ 意义下的解 𝑓⌈𝑛 2⌉(𝑥)f⌈n 2⌉(x)，要求模 𝑥 𝑛 x n 意义下的解 𝑓(𝑥) =𝑓 𝑛(𝑥)f(x)=f n(x)．

将 𝐺(𝑥,𝑓(𝑥))G(x,f(x)) 对 𝑓(𝑥)f(x) 在 𝑓(𝑥) =𝑓⌈𝑛 2⌉(𝑥)f(x)=f⌈n 2⌉(x) 处进行泰勒展开，有：

+∞∑𝑖=0𝜕𝑖 𝐺𝜕𝑦 𝑖(𝑥,𝑓⌈𝑛 2⌉(𝑥))𝑖!(𝑓(𝑥)−𝑓⌈𝑛 2⌉(𝑥))𝑖≡0(m o d 𝑥 𝑛)∑i=0+∞∂i G∂y i(x,f⌈n 2⌉(x))i!(f(x)−f⌈n 2⌉(x))i≡0(mod x n)

因为 𝑓(𝑥) −𝑓⌈𝑛 2⌉(𝑥)f(x)−f⌈n 2⌉(x) 的最低非零项次数最低为 ⌈𝑛 2⌉⌈n 2⌉，故有：

∀2⩽𝑖:(𝑓(𝑥)−𝑓⌈𝑛 2⌉(𝑥))𝑖≡0(m o d 𝑥 𝑛)∀2⩽i:(f(x)−f⌈n 2⌉(x))i≡0(mod x n)

则：

+∞∑𝑖=0𝜕𝑖 𝐺𝜕𝑦 𝑖(𝑥,𝑓⌈𝑛 2⌉(𝑥))𝑖!(𝑓(𝑥)−𝑓⌈𝑛 2⌉(𝑥))𝑖≡𝐺(𝑥,𝑓⌈𝑛 2⌉(𝑥))+𝜕𝐺𝜕𝑦(𝑥,𝑓⌈𝑛 2⌉(𝑥))[𝑓(𝑥)−𝑓⌈𝑛 2⌉(𝑥)]≡0(m o d 𝑥 𝑛)∑i=0+∞∂i G∂y i(x,f⌈n 2⌉(x))i!(f(x)−f⌈n 2⌉(x))i≡G(x,f⌈n 2⌉(x))+∂G∂y(x,f⌈n 2⌉(x))[f(x)−f⌈n 2⌉(x)]≡0(mod x n)𝑓 𝑛(𝑥)≡𝑓⌈𝑛 2⌉(𝑥)−𝐺(𝑥,𝑓⌈𝑛 2⌉(𝑥))𝜕𝐺𝜕𝑦(𝑥,𝑓⌈𝑛 2⌉(𝑥))(m o d 𝑥 𝑛)f n(x)≡f⌈n 2⌉(x)−G(x,f⌈n 2⌉(x))∂G∂y(x,f⌈n 2⌉(x))(mod x n)

或者

𝑓 2 𝑛(𝑥)≡𝑓 𝑛(𝑥)−𝐺(𝑥,𝑓 𝑛(𝑥))𝜕𝐺𝜕𝑦(𝑥,𝑓 𝑛(𝑥))(m o d 𝑥 2 𝑛)f 2 n(x)≡f n(x)−G(x,f n(x))∂G∂y(x,f n(x))(mod x 2 n)

## 例题

### 多项式求逆

设给定函数为 ℎ(𝑥)h(x)，有：

𝐺(𝑥,𝑦)=1 𝑦−ℎ(𝑥)G(x,y)=1 y−h(x)

应用 Newton's Method 可得：

𝑓 2 𝑛(𝑥)≡𝑓 𝑛(𝑥)−1/𝑓 𝑛(𝑥)−ℎ(𝑥)−1/𝑓 2 𝑛(𝑥)(m o d 𝑥 2 𝑛)≡2 𝑓 𝑛(𝑥)−𝑓 2 𝑛(𝑥)ℎ(𝑥)(m o d 𝑥 2 𝑛)f 2 n(x)≡f n(x)−1/f n(x)−h(x)−1/f n 2(x)(mod x 2 n)≡2 f n(x)−f n 2(x)h(x)(mod x 2 n)

时间复杂度

𝑇(𝑛)=𝑇(𝑛 2)+𝑂(𝑛 l o g⁡𝑛)=𝑂(𝑛 l o g⁡𝑛)T(n)=T(n 2)+O(n log⁡n)=O(n log⁡n)

### 多项式开方

设给定函数为 ℎ(𝑥)h(x)，有：

𝐺(𝑥,𝑦)=𝑦 2−ℎ(𝑥)≡0 G(x,y)=y 2−h(x)≡0

应用 Newton's Method 可得：

𝑓 2 𝑛(𝑥)≡𝑓 𝑛(𝑥)−𝑓 2 𝑛(𝑥)−ℎ(𝑥)2 𝑓 𝑛(𝑥)(m o d 𝑥 2 𝑛)≡𝑓 2 𝑛(𝑥)+ℎ(𝑥)2 𝑓 𝑛(𝑥)(m o d 𝑥 2 𝑛)f 2 n(x)≡f n(x)−f n 2(x)−h(x)2 f n(x)(mod x 2 n)≡f n 2(x)+h(x)2 f n(x)(mod x 2 n)

时间复杂度

𝑇(𝑛)=𝑇(𝑛 2)+𝑂(𝑛 l o g⁡𝑛)=𝑂(𝑛 l o g⁡𝑛)T(n)=T(n 2)+O(n log⁡n)=O(n log⁡n)

### 多项式指数函数

设给定函数为 ℎ(𝑥)h(x)，有：

𝐺(𝑥,𝑦)=l n⁡𝑦−ℎ(𝑥)G(x,y)=ln⁡y−h(x)

应用 Newton's Method 可得：

𝑓 2 𝑛(𝑥)≡𝑓 𝑛(𝑥)−l n⁡𝑓 𝑛(𝑥)−ℎ(𝑥)1/𝑓 𝑛(𝑥)(m o d 𝑥 2 𝑛)≡𝑓 𝑛(𝑥)(1−l n⁡𝑓 𝑛(𝑥)+ℎ(𝑥))(m o d 𝑥 2 𝑛)f 2 n(x)≡f n(x)−ln⁡f n(x)−h(x)1/f n(x)(mod x 2 n)≡f n(x)(1−ln⁡f n(x)+h(x))(mod x 2 n)

时间复杂度

𝑇(𝑛)=𝑇(𝑛 2)+𝑂(𝑛 l o g⁡𝑛)=𝑂(𝑛 l o g⁡𝑛)T(n)=T(n 2)+O(n log⁡n)=O(n log⁡n)

## 手算演示

为了方便理解，这里举几个例子演示一下算法流程．

### 复数多项式模多项式的平方根

假设 ℎ h 是一个不被 𝑥 x 整除（有常数项）的复数多项式，求它对模 𝑥 𝑛 x n 的平方根．

我们有方程：

𝐺(𝑓(𝑥))=𝑓 2(𝑥)−ℎ(𝑥)≡0(m o d 𝑥 𝑛)G(f(x))=f 2(x)−h(x)≡0(mod x n)

Taylor 展开 𝐺 G 得到下式．注意这里是对 𝑓 f 的展开，所以导数都是对 𝑓 f 的偏导数，𝑥 x 在这里是当成常数算的．

𝐺(𝑓(𝑥))=+∞∑𝑖=0 𝐺(𝑖)(𝑓 0(𝑥))𝑖!(𝑓(𝑥)−𝑓 0(𝑥))𝑖=𝐺(𝑓 0(𝑥))+2 𝑓 0(𝑥)(𝑓(𝑥)−𝑓 0(𝑥))+(𝑓(𝑥)−𝑓 0(𝑥))2 G(f(x))=∑i=0+∞G(i)(f 0(x))i!(f(x)−f 0(x))i=G(f 0(x))+2 f 0(x)(f(x)−f 0(x))+(f(x)−f 0(x))2

用倍增计算．假设倍增中的中间结果是 𝑓 0(𝑥),𝑓 1(𝑥),…,𝑓 𝑗(𝑥)f 0(x),f 1(x),…,f j(x)，或者数学严谨地说 𝑓 𝑗(𝑥)f j(x) 是满足 𝐺(𝑓 𝑗(𝑥)) ≡0(m o d 𝑥 2 𝑗)G(f j(x))≡0(mod x 2 j) 的一个复数多项式，且为了唯一性它同时满足以下两个条件：

- 𝑓 𝑗(𝑥)f j(x) 次数不超过 𝑥 2 𝑗 x 2 j；
- 𝑓 𝑗+𝑘(𝑥) −𝑓 𝑗(𝑥) ≡0(m o d 𝑥 2 𝑗)f j+k(x)−f j(x)≡0(mod x 2 j)，对所有 𝑘 k．

把 𝑓 𝑗+1(𝑥)f j+1(x) 和 𝑓 𝑗(𝑥)f j(x) 代入上面的式子就有：

𝐺(𝑓 𝑗+1(𝑥))=𝐺(𝑓 𝑗(𝑥))+2 𝑓 𝑗(𝑓 𝑗+1(𝑥)−𝑓 𝑗(𝑥))+(𝑓 𝑗+1(𝑥)−𝑓 𝑗(𝑥))2≡0(m o d 𝑥 2 𝑗+1)G(f j+1(x))=G(f j(x))+2 f j(f j+1(x)−f j(x))+(f j+1(x)−f j(x))2≡0(mod x 2 j+1)

显然 𝑓 𝑗+1(𝑥) −𝑓 𝑗(𝑥)f j+1(x)−f j(x) 必然是 𝑥 2 𝑗 x 2 j 的倍数．于是得到

𝑓 𝑗+1(𝑥)≡𝑓 𝑗(𝑥)−𝑓 2 𝑗(𝑥)−ℎ(𝑥)2 𝑓 𝑗(𝑥)≡𝑓 𝑗(𝑥)2+ℎ(𝑥)2 𝑓 𝑗(𝑥)(m o d 𝑥 2 𝑗+1)f j+1(x)≡f j(x)−f j 2(x)−h(x)2 f j(x)≡f j(x)2+h(x)2 f j(x)(mod x 2 j+1)

如果 𝑓 𝑗(𝑥)f j(x) 存在，那么 2 𝑓 𝑗(𝑥)2 f j(x) 不被 𝑥 x 整除（有常数项），所以必然有模 𝑥 2 𝑗+1 x 2 j+1 的逆元．因此数列 𝑓 0,𝑓 1…,𝑓 𝑗 f 0,f 1…,f j 存在当且仅当 𝑓 0 f 0 存在．不被 𝑥 x 整除的复数多项式 ℎ(𝑥)h(x) 模 𝑥 x 的平方根是一定存在的，因为 ℎ(𝑥)h(x) 模掉 𝑥 x 就是个普通非零复数，一定有两个平方根．所以可以对所有有常数项的 ℎ(𝑥)h(x) 用这个算法．

选 ℎ(𝑥) =𝑥 +1 h(x)=x+1 举例计算如下：

- 𝑓 0(𝑥) =1 f 0(x)=1,𝑓 1(𝑥) =1 2+𝑥+1 2×1 m o d 𝑥 2 =1 2 𝑥 +1 f 1(x)=1 2+x+1 2×1 mod x 2=1 2 x+1,𝑓 2(𝑥) =(1 2 𝑥+1)2+𝑥+1 2×(1 2 𝑥+1)m o d 𝑥 4 =1 1 6 𝑥 3 −1 8 𝑥 2 +1 2 𝑥 +1 f 2(x)=(1 2 x+1)2+x+1 2×(1 2 x+1)mod x 4=1 16 x 3−1 8 x 2+1 2 x+1,……
- 𝑓 0(𝑥) = −1 f 0(x)=−1,𝑓 1(𝑥) =(−1)2+𝑥+1 2×(−1)m o d 𝑥 2 = −1 2 𝑥 −1 f 1(x)=(−1)2+x+1 2×(−1)mod x 2=−1 2 x−1,……（等于前一个取负）

可以验证两个都是正确的模平方根多项式列．

### 整数模素数幂的平方根

牛顿迭代算法还可以迁移到整数模素数的幂的情况． 假设 ℎ h 是一个不被 3 整除的「方便的」整数．（「方便」指「必然有解」，具体条件后文再言）假设要算 ℎ h 在模 3 𝑛 3 n 意义下的平方根 𝑓 f．有方程：

𝐺(𝑓)=𝑓 2−ℎ≡0(m o d 3 𝑛)G(f)=f 2−h≡0(mod 3 n)

Taylor 展开 𝐺 G 得到：

𝐺(𝑓)=+∞∑𝑖=0 𝐺(𝑖)(𝑓 0)𝑖!(𝑓−𝑓 0)𝑖=𝐺(𝑓 0)+2 𝑓 0(𝑓−𝑓 0)+(𝑓−𝑓 0)2 G(f)=∑i=0+∞G(i)(f 0)i!(f−f 0)i=G(f 0)+2 f 0(f−f 0)+(f−f 0)2

用倍增计算．假设倍增中得到的中间结果是 𝑓 0,𝑓 1,…,𝑓 𝑗 f 0,f 1,…,f j，或者严谨地说 𝑓 𝑗 f j 是满足 𝐺(𝑓 𝑗) ≡0(m o d 3 2 𝑗)G(f j)≡0(mod 3 2 j) 的一个整数，且为了唯一性它同时满足以下两个条件：

- 0 <𝑓 𝑗 <3 2 𝑗 0<f j<3 2 j；
- 𝑓 𝑗+𝑘 −𝑓 𝑗 ≡0(m o d 3 2 𝑗)f j+k−f j≡0(mod 3 2 j)，对所有 𝑘 k．

把 𝑓 𝑗+1 f j+1 和 𝑓 𝑗 f j 代入上面的式子就有：

𝐺(𝑓 𝑗+1)=𝐺(𝑓 𝑗)+2 𝑓 𝑗(𝑓 𝑗+1−𝑓 𝑗)+(𝑓 𝑗+1−𝑓 𝑗)2≡0(m o d 3 2 𝑗+1)G(f j+1)=G(f j)+2 f j(f j+1−f j)+(f j+1−f j)2≡0(mod 3 2 j+1)

显然 𝑓 𝑗+1 −𝑓 𝑗 f j+1−f j 必然是 3 2 𝑗 3 2 j 的倍数．于是得到

𝑓 𝑗+1≡𝑓 𝑗−𝑓 2 𝑗−ℎ 2 𝑓 𝑗≡𝑓 2 𝑗+ℎ 2 𝑓 𝑗(m o d 3 2 𝑗+1)f j+1≡f j−f j 2−h 2 f j≡f j 2+h 2 f j(mod 3 2 j+1)

如果 𝑓 𝑗 f j 存在，那么 2 𝑓 𝑗 2 f j 不被 3 3 整除，所以必然有模 3 2 𝑗+1 3 2 j+1 的逆元．因此数列 𝑓 0,𝑓 1…,𝑓 𝑗 f 0,f 1…,f j 存在当且仅当 𝑓 0 f 0 存在．不被 3 整除的整数 ℎ h 模 3 3 的平方根要么不存在，要么有两个．所以 ℎ h 有模 3 3 平方根就是整个算法能跑的唯一条件．

这里选 ℎ =4 6 h=46 实际计算示例．

- 𝑓 0 =1 f 0=1,𝑓 1 =1 2+4 6 2×1 m o d 9 =1 f 1=1 2+46 2×1 mod 9=1,𝑓 2 =1 2+4 6 2×1 m o d 8 1 =6 4 f 2=1 2+46 2×1 mod 81=64,𝑓 3 =6 4 2+4 6 2×6 4 m o d 6 5 6 1 =9 5 5 f 3=64 2+46 2×64 mod 6561=955,……
- 𝑓 0 =2 f 0=2,𝑓 1 =2 2+4 6 2×2 m o d 9 =8 f 1=2 2+46 2×2 mod 9=8,𝑓 2 =8 2+4 6 2×8 m o d 8 1 =1 7 f 2=8 2+46 2×8 mod 81=17,𝑓 3 =1 7 2+4 6 2×1 7 m o d 6 5 6 1 =5 6 0 6 f 3=17 2+46 2×17 mod 6561=5606,……（等于前一个取负）

可以验证一下两个都是正确的模平方根数列．

## 代数证明

这一节对前文进行引申，用抽象代数的语言证明只要 𝑓 f 满足初始解条件，牛顿法对所有的 𝑛 n 都能给出解，并且可以得到全部的解．

### 有解的证明

引理 1

设 整环 𝑅 R 有多项式或 形式幂级数 𝑓(𝑋) =∑𝑖≥0 𝑎 𝑖 𝑋 𝑖 f(X)=∑i≥0 a i X i 和 𝑟,𝑝 ∈𝑅 r,p∈R 使得 𝑓(𝑟) ∈𝑅 𝑝 f(r)∈R p（亦即 𝑟 r 是 𝑓(𝑋)f(X) 在模 𝑝 p 意义下的根）且 𝑓′(𝑟) ∈𝑅 f′(r)∈R 在模 𝑝 p 意义下是可逆的．这里 𝑓′(𝑋) :=∑𝑖≥0(𝑖 +1)𝑎 𝑖+1 𝑋 𝑖 f′(X):=∑i≥0(i+1)a i+1 X i 是 𝑓(𝑋)f(X) 的 形式导数．那么 𝑓(𝑟−𝑓(𝑟)𝑓′(𝑟)) ≡0(m o d 𝑝 2)f(r−f(r)f′(r))≡0(mod p 2)．

证明

对所有 𝑠 ∈𝑅 s∈R，

𝑓(𝑟+𝑠 𝑝)=∑𝑖≥0 𝑎 𝑖(𝑟+𝑠 𝑝)𝑖=∑𝑖≥0 𝑎 𝑖 𝑟 𝑖+𝑠 𝑝∑𝑖≥1 𝑖 𝑎 𝑖 𝑟 𝑖−1+𝑠 2 𝑝 2(…)=𝑓(𝑟)+𝑠 𝑝 𝑓′(𝑟)+𝑠 2 𝑝 2(𝑓″(𝑟)2!+⋯),f(r+s p)=∑i≥0 a i(r+s p)i=∑i≥0 a i r i+s p∑i≥1 i a i r i−1+s 2 p 2(…)=f(r)+s p f′(r)+s 2 p 2(f″(r)2!+⋯),

所以

𝑓(𝑟+𝑠 𝑝)∈𝑅 𝑝 2⟺𝑓(𝑟)+𝑓′(𝑟)𝑠 𝑝∈𝑅 𝑝 2 f(r+s p)∈R p 2⟺f(r)+f′(r)s p∈R p 2

因为 𝑓(𝑟) ∈𝑅 𝑝 f(r)∈R p，且 𝑓′(𝑟)f′(r) 可逆，所以取 𝑠 𝑝 = −𝑓(𝑟)𝑓′(𝑟)s p=−f(r)f′(r) 即可，这里 1 𝑓′(𝑟)1 f′(r) 是模 𝑝 2 p 2 意义下的逆元．因为 𝑓′(𝑟)f′(r) 在模 𝑝 p 意义下可逆，所以它在模 𝑝 2 p 2 意义下也必定存在逆元：设有 𝑎,𝑏,𝑐 ∈𝑅 a,b,c∈R 使 𝑎 𝑓′(𝑟) =𝑏 𝑝 +1 a f′(r)=b p+1 和 𝑓(𝑟) =𝑐 𝑝 f(r)=c p，那么 (𝑎 2 𝑓′(𝑟)−2)𝑓′(𝑟) =𝑏 2 𝑝 2 +1(a 2 f′(r)−2)f′(r)=b 2 p 2+1，故可以取 𝑠 =𝑐(2 −𝑎 2 𝑓′(𝑟))s=c(2−a 2 f′(r))．

对于域 𝑘 k 上的多项式环 𝑘[𝑋]k[X]，设有 𝐺(𝑋,𝑌) ∈𝑘[𝑋,𝑌]G(X,Y)∈k[X,Y] 和 𝑓 𝑛 ∈𝑘[𝑋]f n∈k[X] 使 𝐺(𝑋,𝑓 𝑛(𝑋)) ∈𝑘[𝑋]𝑋 𝑛 G(X,f n(X))∈k[X]X n，那么应用引理 1 就可得到

𝐺(𝑋,𝑓 𝑛(𝑋)−𝐺(𝑋,𝑓 𝑛(𝑋))𝜕𝐺𝜕𝑌(𝑋,𝑓 𝑛(𝑋)))≡0(m o d 𝑋 2 𝑛)G(X,f n(X)−G(X,f n(X))∂G∂Y(X,f n(X)))≡0(mod X 2 n)

而倍增的初始条件只要有 𝑓 1 ∈𝑘 f 1∈k 使得 𝐺(𝑋,𝑓 1) ≡0(m o d 𝑋)G(X,f 1)≡0(mod X) 和 𝜕𝐺𝜕𝑌(𝑋,𝑓 1) ≢0(m o d 𝑋)∂G∂Y(X,f 1)≢0(mod X)．后一个条件保证了 𝜕𝐺𝜕𝑌∂G∂Y 有非零常数项，同时因为 𝑋∣𝐺(𝑋,𝑓 𝑛(𝑋))𝜕𝐺𝜕𝑌(𝑋,𝑓 𝑛(𝑋))X|G(X,f n(X))∂G∂Y(X,f n(X))，故而对所有的 𝑛 n，𝜕𝐺𝜕𝑌(𝑋,𝑓 𝑛)∂G∂Y(X,f n) 总是模 𝑋 𝑛 X n 意义下可逆的，也就满足了下一次迭代的条件．

### 得到全部解的证明

引理 2

若 𝑅 R 为 UFD，𝑓,𝑟,𝑝 f,r,p 定义同引理 1．则引理 1 给出的 𝑟 −𝑓(𝑟)𝑓′(𝑟)r−f(r)f′(r) 是模 𝑝 2 p 2 意义下唯一满足以下两条件的 𝑥 x 的值：

- 𝑓(𝑥) ∈𝑅 𝑝 2 f(x)∈R p 2
- 𝑥 −𝑟 ∈𝑅 𝑝 x−r∈R p

亦即

∀𝑥∈𝑅,𝑝 2∣𝑓(𝑥)∧𝑝∣(𝑥−𝑟)⟹𝑥≡𝑟−𝑓(𝑟)𝑓′(𝑟)(m o d 𝑝 2)∀x∈R,p 2∣f(x)∧p∣(x−r)⟹x≡r−f(r)f′(r)(mod p 2)
证明

令 𝑠 = −𝑓(𝑟)𝑓′(𝑟)𝑝 s=−f(r)f′(r)p 和 𝑢 =𝑟 +𝑠 𝑝 u=r+s p，引理 1 保证 𝑢 u 满足两个条件，且 𝑓(𝑟) +𝑓′(𝑟)𝑠 𝑝 ∈𝑅 𝑝 2 f(r)+f′(r)s p∈R p 2． 设 𝑣 v 是满足上述条件的值，则有 𝑣 =𝑟 +𝑡 𝑝 v=r+t p 和 𝑓(𝑟) +𝑓′(𝑟)𝑡 𝑝 ∈𝑅 𝑝 2 f(r)+f′(r)t p∈R p 2． 于是有 𝑓′(𝑟)(𝑡 −𝑠)𝑝 ∈𝑅 𝑝 2 f′(r)(t−s)p∈R p 2 和 𝑣 −𝑢 ∈𝑅 𝑝 2 v−u∈R p 2．

牛顿法可以保证得到模 𝑋 2 𝑛 X 2 n 的全部解．假设 𝐺(𝑋,ℎ) ≡0(m o d 𝑋 2 𝑛)G(X,h)≡0(mod X 2 n)，那么令 ℎ 2 𝑖 :=ℎ(m o d 𝑋 2 𝑖)h 2 i:=h(mod X 2 i)，然后取 𝑓 1 =ℎ 1 f 1=h 1 并用牛顿法，根据引理 2 可得 𝑓 2 𝑖 ≡ℎ 2 𝑖(m o d 𝑋 2 𝑖)f 2 i≡h 2 i(mod X 2 i)，所以一定有 𝑓 2 𝑛 =ℎ f 2 n=h．

上面的论证也说明了，在 𝜕𝐺𝜕𝑦(0,𝑦)∂G∂y(0,y) 永远可逆时，𝐺(𝑋,𝑓) ≡0(m o d 𝑋 𝑛)G(X,f)≡0(mod X n) 的解的个数等于 𝐺(0,𝑓) ≡0(m o d 𝑋)G(0,f)≡0(mod X) 的解的个数．这个结论并非平凡．请看下面的例子．

牛顿法无效时解的个数随次数而变多的例子

模 𝑋 X 意义下 𝑋 2 X 2 的平方根只有 0 0，但是模 𝑋 4 X 4 意义下 𝑋 2 X 2 的平方根有 𝑋, −𝑋,𝑋 3 +𝑋,…X,−X,X 3+X,…．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：fps5283, Marcythm, 97littleleaf11, shuzhouliu, Enter-tainer, H-J-Granger, Ir1d, Tiphereth-A, TrisolarisHD, abc1763613206, c-forrest, CCXXXI, EndlessCheng, Great-designer, hly1204, hsfzLZH1, huayucaiji, kenlig, ksyx, ouuan, SamZhangQingChuan, sshwy, StudyingFather, test12345-pupil, untitledunrevised, zjkmxy
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用