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$
7
  • 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$ Commented Aug 6, 2016 at 20:04
  • $\begingroup$ Are these unsigned integers or two's compliment integers? They may behave differently with a bitwise XOR. $\endgroup$
    – Kajelad
    Commented Aug 6, 2016 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$ Commented Aug 6, 2016 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$ Commented Aug 6, 2016 at 20:40
  • $\begingroup$ @Kajelad They are unsigned integers. $\endgroup$ Commented Aug 6, 2016 at 22:08

1 Answer 1

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$
4
  • $\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$ Commented Aug 10, 2016 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$ Commented Aug 10, 2016 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$ Commented Aug 10, 2016 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$ Commented Aug 11, 2016 at 5:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .