1
$\begingroup$

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

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

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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}$. $\endgroup$ Jul 28, 2015 at 3:15
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Jul 28, 2015 at 4:29
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ What if we're talking about RSA, where $n > 2^{2047}$? Then we could have $j = 2^{100}$ and still be considered very small. $\endgroup$ Jul 26, 2015 at 2:58
  • $\begingroup$ Also, what about the case where $j = O(n)$? $\endgroup$ Jul 26, 2015 at 2:58
  • $\begingroup$ 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. $\endgroup$
    – user1338
    Jul 26, 2015 at 13:09
  • $\begingroup$ I know... I was wondering about more sophisticated techniques, say if I know it's within $N/4$ of a power of two. $\endgroup$ Jul 26, 2015 at 13:32

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.