多项式牛顿迭代
设
[f(g(x))equiv 0 (mod x^n)
]
求出此模意义下的(g(x))
当(n=1)时，单独求出([x^0]f(g(x)))
假设已经得到了模(x^{lceilfrac{n}{2} ceil})意义下的解(g_0(x))，要求模(x^{n})意义下的解(g(x))
将(f(g(x)))在(g_0(x))处泰勒展开得到
[sum_{n}frac{f^{(n)}(g_0(x))}{n!}(g(x)-g_0(x))^nequiv 0 (mod x^n)
]
因为(g(x)-g_0(x))的最低非零次项的次数为(lceilfrac{n}{2} ceil)，故有
[forall ngeq 2,(g(x)-g_0(x))^nequiv 0 (mod x^n)
]
则
[sum_{n}frac{f^{(n)}(g_0(x))}{n!}(g(x)-g_0(x))^nequiv f(g_0(x))+f'(g_0(x))(g(x)-g_0(x)) (mod x^n)\
g(x)equiv g_0(x)-frac{f(g_0(x))}{f'(g_0(x))} (mod x^n)\
]