Reconstructing RSA Private Keys from Random Key Bits

https://eprint.iacr.org/2008/510.pdf

$p, q$ あたりの一部のbitがわかっている時に polynomial time decisional algorithmでNを素因数分解する

[* Lifting solutions mod $2^i$ ]

$0$ から $i - 1$ bitまでわかっている時、 $i$ bitを推定する。ここで、Hensel's Liftを使って、 $\mod 2^i$ での解から、 $\mod 2^{i+1}$ での解を求める感じ

Multivariate Hensel's Lemma

ある $n$ 次多項式 $f(x_1, x_2, \dots, x_n) \mod \pi^i$ に対してその根 $\vec{r} = (r_1, r_2, \dots, r_n)$ がわかっている時、 $f(x_1, x_2, \dots, x_n) \mod \pi^{i+1}$ の根 $\vec{r} + \vec{b}$ を次の様に求めることができる