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?

  • 2
    $\begingroup$ Note: the "both $p$ and $q$" part of the question is pointless: when the low-order $x$ bits $p_{[x]}$ of $p$ leak, we can find the low-order $x$ bits $q_{[x]}$ of $q$ as ${p_{[x]}}^{-1}N\bmod2^x=q_{[x]}$. $\endgroup$
    – fgrieu
    Jan 4, 2020 at 16:21

1 Answer 1


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.

The closest article is by Maira et. al.

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$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.