# Integer factorization with additional knowledge of $p \oplus q$

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.

## 1 Answer

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)

• 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$. Jan 7, 2017 at 15:01
• @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. Jan 7, 2017 at 16:07
• 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.$ Jan 8, 2017 at 0:09
• 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. Jan 8, 2017 at 12:28
• @SamiLiedes: cool; I was about to do that myself; you beat me to it. And, "hundreds to thousands" is consistent with my experience with this sort of algorithm applied to other scenarios with the same branching factors Jan 8, 2017 at 15:54