# 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

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$.
// TODO(yberman) do code

• 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