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

• Can you define precisely what you mean by "very small?"
– user1338
Jul 26, 2015 at 1:20

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.

• 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}$. Jul 28, 2015 at 3:15
• @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.
Jul 28, 2015 at 4:29

I will assume that when you say that a natural number n is "very small," that you mean that for some constant j, n < j.

Given n and a promise that its prime factors p,q, are both within j of 2^b for some natural number b and some natural constant j, it's not hard to construct a brute-force algorithm that checks every possible value of p and q in time polynomial in the size of n.

Here's a quick example:

Let j = 20, and let n = 1018081.

We are guaranteed that the prime factors of n are within 20 of a power of 2.

So we need only consider every m s.t. m +/- 20 <= (2^b) for some b.

These values include:

                           1, 2, 3, 4,   ... ,    21
1, 2, 3, 4, 5,   ... ,    22
1, 2, 3, 4, 5, 6, 7,   ... ,    24
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... ,    28
...
236, ... , 254, 255, 256, 257, 258, ... ,   276
492, ... , 510, 511, 512, 513, 514, ... ,   532
1004, ... , 1022, 1023, 1024, 1025, 1026, ..., 1044


Because we know that 1024 * 1024 > 1018081, it's clear that we don't need to go beyond 1024 in our list. This is because we are limited to only two prime factors close to a power of 2.

It ought to be clear that given an integer n, the number of values that need to be tested as prime factors of n is roughly: (2 j + 1)*(ceil(ln(n)/ln(2))). This means that the "naive" algorithm is good enough in this case.

(Incidentally, the prime factors of 1018081 are 1009 and 1009, so you might want to try a harder example if you decide to code it.)

• What if we're talking about RSA, where $n > 2^{2047}$? Then we could have $j = 2^{100}$ and still be considered very small. Jul 26, 2015 at 2:58
• Also, what about the case where $j = O(n)$? Jul 26, 2015 at 2:58
• I think that if j = O(n), then the naive algorithm ceases to be polynomial time. This is because "very small" could be as large as the number itself. On the other hand, if j is constant or O(log n), then I believe that the algorithm will remain polynomial time. I don't think it's likely you'll break RSA with such a simple approach, though...not that you said that was your goal.
– user1338
Jul 26, 2015 at 13:09
• I know... I was wondering about more sophisticated techniques, say if I know it's within $N/4$ of a power of two. Jul 26, 2015 at 13:32