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

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$. – Thomas Jan 7 '17 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. – poncho Jan 7 '17 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.$ – kodlu Jan 8 '17 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. – Sami Liedes Jan 8 '17 at 12:28
• Can you post your code somewhere? Sounds interesting. – user13741 Jan 8 '17 at 14:06