<p>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:</p>

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

<p>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.</p>

CC BY-SA 3.0
2015-07-28T03:15:10.890Z
How do you read off $k_pk_q$ and $k_p + k_q$ with those inequalities? I think you meant to write $k_p + k_q \leq 2^{b/2 + 1}$.
Elliot Gorokhovsky
CC BY-SA 3.0
2015-07-28T04:29:00.870Z
@RenéG, I've updated my answer to explain how to read them off.  Also if $k_p < 2^{b/2}$ and $k_q < 2^{b/2}$, then it follows that $k_p k_q < 2^b$ and $k_p + k_q < 2^{b/2+1}$, so I think my conditions are correct.  I did not try to optimize to make them the loosest possible conditions.
D.W.
CC BY-SA 3.0
2015-07-27T22:45:00.157Z
2015-07-28T04:27:55.697Z
2015-07-28T04:27:55.697Z
D.W.
<p>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$?</p>

<cr.crypto-security><factoring>
Factoring semiprimes whose factors very close to a power of two
Elliot Gorokhovsky
# Factoring semiprimes whose factors very close to a power of two

(Asked by: username_0 on 2015-07-25)

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

**Tags:** cr.crypto-security, factoring

---

## 1 answers

### Answer by username_1 on 2015-07-27. Score: 3 | Accepted answer

If $0 \le k\_p < 2^{b/2}$ and $0 \le k\_q < 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 < 2^b$ and $0 \le k\_p+k\_q < 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.

> **Comments:**
> **username_0**: How do you read off $k_pk_q$ and $k_p + k_q$ with those inequalities? I think you meant to write $k_p + k_q \leq 2^{b/2 + 1}$.  
> **username_1**: @RenéG, I've updated my answer to explain how to read them off.  Also if $k_p < 2^{b/2}$ and $k_q < 2^{b/2}$, then it follows that $k_p k_q < 2^b$ and $k_p + k_q < 2^{b/2+1}$, so I think my conditions are correct.  I did not try to optimize to make them the loosest possible conditions.  

---

