algorithm - 求多项式模 2^r 的根

Question

我有一个多项式 P，我想找到 y 使得 P(y) = 0 模 2^r。

我已经尝试过类似 Hensel 提升的方法，但我不知道这是否可行，因为通常情况 f'(y mod 2) != 0 mod 2 这通常不是真的。

有不同的算法可用吗？或者 Hensel 升降机的变体可以工作吗？

提前致谢

Answer 1

假设您有这样的解决a方案f(a) = 0 mod 2^p。要做一个亨塞尔电梯以获得一个解决方案mod 2^(p+1)，你最终需要解决

f'(a)*t = -f(a)/2^(p+1) mod 2

为t.

如果f'(a) = 0 mod 2，有两种可能：

如果 2 不除f(a)/2^(p+1)，则没有mod 2^(p+1)由 的值产生的解（或 2 的任何更高的幂）a。

如果 2 除数f(a)/2^(p+1)，则 0 和 1 都可以作为 t 的可接受值，如果您希望找到所有解决方案，则需要对它们中的每一个进行单独的提升mod 2^r。

请注意，a它在每一步的范围内[0,2^p)，因此当您求解 时t，您正在评估f(x)和f'(x)，x=a而不是x=a mod 2。