0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you know $z$? $2^{32}$ is small. Is brute force a valid answer? $\endgroup$ – yberman Apr 23 '17 at 1:17
  • $\begingroup$ @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. $\endgroup$ – Justin Sapp Apr 23 '17 at 1:30
  • $\begingroup$ 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? $\endgroup$ – Χpẘ Apr 23 '17 at 1:52
  • $\begingroup$ I have an idea. @JustinSapp pick a programming language that you like. C? $\endgroup$ – yberman Apr 23 '17 at 1:53
  • $\begingroup$ @Χpẘ I'm trying to solve for $x$ (a.k.a. isolate $x$ from the rest of the equation). $\endgroup$ – Justin Sapp Apr 23 '17 at 1:59
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Χpẘ Apr 24 '17 at 1:20
  • $\begingroup$ 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. $\endgroup$ – yberman Apr 24 '17 at 11:13

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.