Given two unknown large primes $p$ and $q$, can we efficiently factor $n=pq$ if we additionally know $p \oplus q$ (bitwise XOR of the primes)?

EDIT: I have implemented the algorithm described in poncho's answer in this Python code.


I believe that we can indeed factor efficiently.

Consider this factoring algorithm; we track the set of $k$ bit values $p_k, q_k$ that satisfy $p_k \times q_k \equiv n \bmod 2^k$; for each iteration, we attempt to extend $p_k, q_k$ by one bit, generating 0-4 possible solutions $p_{k+1}, q_{k+1}$ that satisfy $p_{k+1} \times q_{k+1} \equiv n \bmod 2^{k+1}$.

Now, when we apply this approach to the standard factorization method, it fails miserable; it turns out there will always be 2 solutions at step $k+1$ for every solution at step $k$ (and hence we have an exponential time solution).

However, if we add the additional constraint that $p_k \oplus q_k = m$ (where $m$ is the known value of $p \oplus q$, this drastically reduces the number of intermediate solutions. I believe what will happen is that, when we are at a specific $p_k, q_k$, half the time, there will be 0 solutions for step $k+1$ (and hence we can eliminate that branch of the tree), and half the time, there will be 2 solutions. What this gives us is a fairly slowly growing number of solutions overall as we increase $k$; this makes it totally feasible to get to $k = \log_2{n}$ (and, at which point, we can check the intermediate solutions directly)

  • 2
    $\begingroup$ Isn't it still exponential though? If you only branch half the time on average, then you square-root the size of the search space as far as I know, so I don't see how it is feasible to get to $k = \log_2 n$. $\endgroup$ – Thomas Jan 7 '17 at 15:01
  • $\begingroup$ @Thomas: I've done this sort of state scanning attack before in other contexts; for an expected branch factor of 1, the amount of state tends to grow slowly. Think about this way; if the number of possible solutions at step k in $z$, half of those solutions will die (have 0 solutions) at step k+1, and the other half will have 2 solutions, and so at step k+1, you'll still have approximately $z$ solutions. $\endgroup$ – poncho Jan 7 '17 at 16:07
  • $\begingroup$ I agree with @Thomas, if you write the update equations, you see that there are either 2 or zero solutions, but for sizeable $n$ by chernoff bound you will have 2 solutions at least $(v-\sqrt{v})/2\sim v/2$ times with probability approaching one, where $v=\log_2 n$, so overall number of solutions surviving at the end is $\approx 2^{v/2}=\sqrt{n}$ which is exponential in the bit size $v.$ $\endgroup$ – kodlu Jan 8 '17 at 0:09
  • $\begingroup$ Ok, I wrote a Python implementation to test this, and it indeed works: Given $pq$ and $p \oplus q$ where $p$ and $q$ are 1024-bit primes, I can factor $pq$. The size of the tracked set seems to generally be in the hundreds-to-thousands range. $\endgroup$ – Sami Liedes Jan 8 '17 at 12:28
  • $\begingroup$ Can you post your code somewhere? Sounds interesting. $\endgroup$ – user13741 Jan 8 '17 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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