RSA: If the least significant bits of the factors are leaked, what advantage is there in factoring N? For $N=pq$, if the first $x$ least significant bits of both $p$ and $q$ are leaked.


what is the advantage in factoring $N$?
Does this give an advantage beyond simply lowering the number of bits we have to guess for the smaller factor?
This question looked due to the Cold boot attack, by Halderman et. al. Normally researchers look at some random known bit known due to the decaying of the memory.


2009 Heninger et. al Reconstructing RSA Private Keys from Random Key Bits 

if $\delta = .57$ fraction of the bits of $p$ and $q$ is randomly is given they can construct them.


The closest article is by Maira et. al.


2010 - Maitra Factoring RSA Modulus Using Prime Reconstruction from Random Known Bits, also a slide of one of the authors.

In Section 2 and 3, they look at LSB case. With theorem 1;


Theorem 1: Let $N = pq$, when $p, q$ are primes of same bit size. Let $S = \{0,\ldots, l_{N /4}\}$. Consider $U \subseteq S$ and $V = S \backslash U$. Assume that p[i]’s for $i \in U$ and $q[j]$’s for $j \in V$ are known. Then one can factor $N$ in $poly(\log N)$-time.


$l_N$ the bit size of $N$, i.e, $l_N = \lceil log_2 N\rceil$.