非单根的亨泽尔提升：模2¹⁰到2¹⁹的根提升方法咨询

针对你提到的多项式$f(x)=x^{3-9x+8$，已知$x=55$是模$2}{10}$的解且为非单根（$f'(x)\equiv0\pmod{2}$），下面一步步带你完成从模$2^{10}$到$2{19}$的根提升：

第一步：分析导数与函数值的2-adic赋值 #

首先明确两个关键的2-adic赋值（即能被2的几次幂整除）：

• 计算导数$f'(x)=3x^2-9$，代入$x=55$：
  $$f'(55)=3\times55^2 -9=9075-9=9066=2\times4533$$
  4533是奇数，说明$f'(55)$恰好被2整除1次，即$v_2(f'(55))=1$。
• 计算$f(55)$的值：
  $$f(55)=55^{3-9\times55+8=166375-495+8=165888=2}{11}\times81$$
  说明$f(55)$能被$2^{11}$整除，即$v_2(f(55))=11$。

这里$v_2(f(55))=11\geq2\times v_2(f'(55))=2$，满足非单根可提升的条件。

第二步：构造提升后的解形式 #

设模$2^{19}$的解为$a=55 + t\times2^{{10}$，其中$t$是整数。我们需要找到$t$使得$f(a)\equiv0\pmod{2}{19}}$。

利用泰勒展开（忽略模$2^{{19}$下为0的高次项，因为$(2}{10})²⁼²{20}>2^{19}$）：
$$f(55+t\times2^{10})\equiv f(55) + f'(55)\times t\times2^{10}\pmod{2{19}}$$

代入已知值：
$$2^{11}\times81 + 2\times4533\times t\times2^{{10}\equiv0\pmod{2}{19}}$$

第三步：求解整数t #

对等式两边同时除以$2^{10}$简化：
$$2\times81 + 2\times4533\times t\equiv0\pmod{2^9}$$
再除以2（两边都能被2整除）：
$$81 + 4533\times t\equiv0\pmod{256}$$

先把4533模256简化：$4533=17\times256+181$，所以方程变为：
$$181t\equiv-81\pmod{256}$$
$-81$模256等于175，接下来找181在模256下的逆元。用扩展欧几里得算法可算出逆元为157（验证：$181\times157=27475$，$27475\mod256=1$）。

计算t：
$$t\equiv175\times157\pmod{256}$$
$$175\times157=27475, 27475\mod256=83$$
取最小非负解$t=83$。

第四步：得到模$2^{19}$的解 #

代入$a=55+83\times2^{10}$：
$$2^{10}=1024, 83\times1024=84992, 55+84992=85047$$

验证：$f(85047)$会被$2^{19}=524288$整除，符合要求。

补充：非单根提升的通用规则 #

当处理模素数幂$p^k$的非单根时：
设$v_p(f'(a))=r$（导数被$p^{r$整除但不被$p}{r+1}$整除），$v_p(f(a))=s$：

• 若$s<r$：不存在提升解；
• 若$r\leq s<2r$：无法提升到$p^{k+1}$；
• 若$s\geq2r$：存在唯一解$b\equiv a\pmod{p^{{k-r}}$，使得$f(b)\equiv0\pmod{p}{k+r}}$，可重复此过程直到达到目标幂次。

内容的提问来源于stack exchange，提问作者Bunneh