5
$\begingroup$

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

$$y = (21306107x - 27776373) \oplus (i - 29799480x) $$

Where:

  • $\oplus$ is the XOR operator for 32-bit integers.
  • Both $y$ and $i$ are known 32-bit integers.
  • $x$ is some unknown 32-bit integer

[Edit: $y$ and $i$ actually do vary, but are fixed for each unknown value of $x$]

$\endgroup$
  • 1
    $\begingroup$ Post constants? XOR and plus, minus and multiplication in one equation is ugly, XOR operates bitwise and the others do normal $\mathbb{Z}$ arithmetic. $\endgroup$ – Maximilian Gerhardt Aug 6 '16 at 20:04
  • $\begingroup$ Are these unsigned integers or two's compliment integers? They may behave differently with a bitwise XOR. $\endgroup$ – Kajelad Aug 6 '16 at 20:07
  • 2
    $\begingroup$ You can do this componentwise, one binary digit at a time, to get a system of equations. If no one gives a better answer I'll come back with an example calculation in a couple days. $\endgroup$ – Charlotte Aten Aug 6 '16 at 20:34
  • $\begingroup$ @MaximilianGerhardt: I probably shouldn't have called them constants, they still vary, but they are known for each situation in which they apply. $\endgroup$ – CaptainObvious Aug 6 '16 at 20:40
  • $\begingroup$ @Kajelad They are unsigned integers. $\endgroup$ – CaptainObvious Aug 6 '16 at 22:08
5
+100
$\begingroup$

Call your equation $y=(Ax+B)\oplus(Cx+D)$, because it saves typing.

Working modulo 2, and using $\alpha_0$ to represent the least significant bit of $\alpha$, your equation implies:

$$y_0=(A_0x_0\oplus B_0)\oplus(C_0x_0\oplus D_0)\text,$$

which, if $A$ is odd and $C$ is even as in your example, gives $y_0=(x_0\oplus B_0)\oplus(0\oplus D_0)$, which means

$$x_0=B_0\oplus D_0\oplus y_0\text.$$

So now we know $x_0$, the least significant bit of $x$.

Next, writing $X=x-x_0$, your equation becomes

$$y=(AX+Ax_0+B)\oplus(CX+Cx_0+D)\text,$$

or, putting $B'=Ax_0+B$ and $D'=Cx_0+D$ (remember that it isn't cheating to do this, because $x_0$ is now a known value),

$$y=(AX+B')\oplus(CX+D')\text.$$

(Note that this implies $y_0=B'_0\oplus{D'_0}$: we'll use this fact in a moment).

It is now possible to shift both sides of the equation to the right by one bit. The shifted equation can be written as $$\frac12 y=(A\frac12 X+\frac12 B')\oplus(C\frac12 X+\frac12 D')\text,$$

using $\frac12$ as a convenient notation for a right shift (losing the least significant bit if the number is odd).

This shift is licit in that it doesn't change the equation as far as the more significant bits of the various numbers are concerned. But you can additionally reassure yourself that $X$ is even and that the discarded least-significant bits satisfy $y_0=B'_0\oplus{D'_0}$, and hence that the equation after the discard is still valid if and only if your original equation is.

Now let's do some rewriting to make this equation look like the one we started with. Put $y^*=\frac12 y$, $x^*=\frac12 X$, $B^*=\frac12 B'$, and $D^*=\frac12 D'$. Then the shifted equation is

$$y^*=(Ax^*+B^*)\oplus(Cx^*+D^*)\text.$$

So now we can go through the whole process again, this time deducing $x^*_0$, the least significant bit of $x^*$ - that is to say, the second least significant bit of $x$ (call it $x_1$ if you like).

Then again, to deduce the third least significant bit, then again... Each repetition of the process generates one more bit of $x$, until you have them all.

Note on parity: As Peter Košinár points out, if $A$ and $C$ are both even or both odd, then we have $x_0$ occurring an even number of times in $y_0=(A_0x_0\oplus B_0)\oplus(C_0x_0\oplus D_0)$, which means that the equation says nothing at all about $x_0$. This means that if $B_0\oplus D_0\oplus y_0=0$ then both $x_0=0$ and $x_0=1$ are possible and if $B_0\oplus D_0\oplus y_0\ne 0$ then there is no solution. In the next round, exactly the same thing happens: if $B^*_0\oplus D^*_0\oplus y_1=0$ then both $x_1=0$ and $x_1=1$ are possible and if $B^*_0\oplus D^*_0\oplus y_1\ne 0$ then there is no solution.

$\endgroup$
  • $\begingroup$ Also can you explain further the derivation of $y_0=(A_0x_0\oplus B_0)\oplus(C_0x_0\oplus D_0)$ please? $\endgroup$ – CaptainObvious Aug 10 '16 at 19:43
  • $\begingroup$ You might also want to mention what happens if $A$ and $C$ are of the same parity -- one either gets two or no solutions. $\endgroup$ – Peter Košinár Aug 10 '16 at 19:57
  • $\begingroup$ $A=21306107$, $C=-29799480$. Modulo 2, each number equals its own least significant bit. Hence $y_0=y$, $A_0=A$, and so on. $\endgroup$ – Martin Kochanski Aug 10 '16 at 21:58
  • $\begingroup$ @MartinKochanski I understand now, thanks. I was finally able to implement your algorithm in code and have now verified that it works. I will reward you the bounty once I can, but for now I'll just accept your answer. $\endgroup$ – CaptainObvious Aug 11 '16 at 5:08

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.