多项式相关

省略所有$\pmod{x^n}$

求逆

$AB=1$

$AC=1\pmod{x^{n/2}}$

$B^2-2BC+C^2=0$

$B-2C+AC^2=0$

$B=2C+AC^2$

除法

$A=DB+R$

$x^nA(\frac{1}{x})=x^{n-m}D(\frac{1}{x})x^m+x^{n-m+1}R(\frac{1}{x})$

$A^R(x)=D^R(x)B^R(x)\pmod{x^{n-m+1}}$

解出 $D$

开根

$B^2=A$

$C^2=A\pmod{x^{n/2}}$

$(B+C)(B-C)=0\pmod{x^{n/2}}$

讨论 $B-C=0\pmod{x^{n/2}}$

$A-2BC+C^2=0$

$B=\dfrac{A+C^2}{2C}$

牛顿迭代

$G(F)=0$,求解 $F$

$G(F_0)=0\pmod{x^{n/2}}$

$G(F)=G(F_0)+\dfrac{G’(F_0)}{1!}(F-F_0)+\dfrac{G’‘(F_0)}{2!}(F-F_0)^2+…$

因为 $F$ 和 $F_0$ 的最后 $n/2$ 项相同,所以 $(F−F_0)^2$ 的最低的非 $0$ 项次数大于等于 $n$

$G(F)=G(F_0)+G’(F_0)(F-F_0)$

$F=F_0-\dfrac{G(F_0)}{G’(F_0)}$

参考链接