Mon*_*ica 5 algorithm math algebra polynomial-math
我有一个多项式P,我想找到y,使P(y)= 0 modulo 2 ^ r.
我尝试了Hensel提升的方法,但我不知道这是否可行,因为通常情况f'(y mod 2)!= 0 mod 2,这通常不正确.
是否有不同的算法可用？或者Hensel提升的变化可以起作用吗？
提前致谢
假设您有一个解决方案，a使得f(a) = 0 mod 2^p. 要进行 Hensel 提升以获得解决方案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)不会产生解（或任何更高的 2 次幂） 。mod 2^(p+1)a
如果 2 整除f(a)/2^(p+1)，那么 0 和 1 都可以作为 t 的可接受值，如果您希望找到所有解决方案，您将需要对它们中的每一个进行单独的提升mod 2^r。
请注意 是在每一步的a范围内[0,2^p)，因此当您求解 时t，您正在评估f(x)和，f'(x)而不是。x=ax=a mod 2