algorithm - 2^r を法とする多項式の根を求める

Question

多項式 P があり、P(y) = 0 modulo 2^r となるような y を見つけたいと思います。

私はヘンセルリフティングに沿って何かを試しましたが、通常は真ではない通常の条件 f'(y mod 2) != 0 mod 2 のため、これが機能するかどうかはわかりません。

利用可能な別のアルゴリズムはありますか? それとも、ヘンゼル リフティングのバリエーションが機能する可能性がありますか?

前もって感謝します

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 つの可能性があります。

2 が を割り切らない場合、この の値から生じるf(a)/2^(p+1)解mod 2^(p+1)(またはそれ以上の 2 の累乗)はありませんa。

除数が 2f(a)/2^(p+1)の場合、0 と 1 の両方が t の許容値として機能し、すべての解を見つけたい場合は、それぞれに対して個別のリフトを実行する必要がありますmod 2^r。

aは各ステップで範囲内にあることに注意してください[0,2^p)。したがって、 について解くと、ではなくでt評価されます。f(x)f'(x)x=ax=a mod 2