Factoring semiprimes whose factors very close to a power of two Are there any factorization algorithms that run well on numbers $N = pq$ where $p,q$ are prime and $p = 2^b - k_p, q = 2^b - k_q$ for very small $k_p,k_q$? What about $p = 2^b + k_p, q = 2^b + k_q$ for very small $k_p,k_q$?
If $0 \le k_p &lt; 2^{b/2}$ and $0 \le k_q &lt; 2^{b/2}$, it's easy to factor such numbers.  Consider:

$$N = pq = (2^b-k_p)(2^b-k_q) = 2^{2b} -(k_p+k_q) 2^b + k_p k_q.$$

Under the stated conditions, you can read off the values of $k_p k_q$ and $k_p+k_q$ from the binary representation of $N$, since $0 \le k_p k_q &lt; 2^b$ and $0 \le k_p+k_q &lt; 2^b$.  In particular, $k_p k_q$ can be obtained as $N \bmod 2^b$, and then you can compute $k_p + k_q$ as $(2^{2b} - N + k_p k_q)/2^b$.  Once you know those values, you can solve for $k_p,k_q$ by solving a quadratic equation (you have a system of 2 equations in 2 unknowns; simple algebra can be used to recover the value of the unknowns).  Once $k_p,k_q$ are known, the factorization of $N$ is immediately revealed.