# Can this equation involving binary operations (XOR) and 32-bit integers be solved?

I need to solve the following equation for $x$:

$$y = (x * (z + A) + B) \oplus (x * z + C)$$

where:

• $\oplus$ is the binary XOR operator for 32-bit integers
• all variables are 32-bit integers
• all variables except for $x$ are known
• the variables $A$, $B$, and $C$ are the constants $32757935$, $-29408451$, and $-5512095$
• EDIT: $z$ isn't a constant, and varies, but is unique for every pair of $x$ and $y$.

If it helps, this problem is based on/similar to this equation: How to solve this equation for $x$ with XOR involved?

• Do you know $z$? $2^{32}$ is small. Is brute force a valid answer? – yberman Apr 23 '17 at 1:17
• @YBerman Yes, $z$ is known and is unique for every value of $x$ and $y$ (it isn't a constant). Bruteforcing isn't an option as I'll need to be doing multiple calculations fast. – Justin Sapp Apr 23 '17 at 1:30
• If $z,A,B,C$ are all known, what's there to solve? Just plug everything into the equation and out comes $y$. Are you looking for a fast algorithm? A factorization? – Χpẘ Apr 23 '17 at 1:52
• I have an idea. @JustinSapp pick a programming language that you like. C? – yberman Apr 23 '17 at 1:53
• @Χpẘ I'm trying to solve for $x$ (a.k.a. isolate $x$ from the rest of the equation). – Justin Sapp Apr 23 '17 at 1:59

## 1 Answer

Note that the three operations $\oplus$, $\times$, and $+$ have the property that modification of the upper bits do not change the lower bits. That is if $\square$ is one of the three operations, $x \square y = z \mod 2^n$ will not change if you substitute $x$ with $x + 2^m$ for $m \geq n$.

So you can do a depth first search populating the lower bits first and checking the partial equality using a mask.

// TODO(yberman) do code


Note I suspect (but do not know) there is no closed form solution, as these operations don't play well together. IDEA uses a mixture of xor, multiply, and add for example. Even just addition and xor is mathematically messy if you allow rotations.

• Seems like that would be lot less efficient (CPU-wise) than just a straightforward calculation. If the compiler already has all the operands in registers, the calculation is around 6 x64 assembly language instructions. But a depth first search would easily take hundreds of instructions. I guess I still haven't figured out what the OP wants. – Χpẘ Apr 24 '17 at 1:20
• He wants a algorithm for given fixed $z$ and $y$ find $x$. Initially I think he thought there would be a closed formula $x =f(y,z)$ which would do the trick. – yberman Apr 24 '17 at 11:13