Solving a system of equations using both arithmetic and bitwise operations

Question

At first I asked this question on Stackoverflow, where I was advised to ask here. So there is the question:

I have a system of pretty simple equations:

1. $x + y = A$
2. $f(x,y) + y = B$

$A, B$ are known. All of the variables are 64-bit positive integers, including $f(x,y)$.

But the problem is that $f(x,y)$ uses bitwise operations:

$$f(x,y) = x \oplus (x \ll 3) \oplus y \oplus (y \gg 14)$$

I tried to solve this by representing arithmetic addition with bitwise opperations and carry-bits. I also tried to represent each bit as a boolean value and then solve a system of boolean equations. I didn't succeed any much. So is there any method of doing this properly?

Answer 1

So is there any method of doing this properly?

Here's the most obvious method:

• Iterate through the lower 14 bits of $y$, that is, you'll perform the below steps for each of the 16384 possible settings of the lower bits of $y$

• Compute what the lower 14 bits of $x$ are, using $x = A - y$ (because the subtraction is modulo $2^{64}$, we can ignore everything higher than bit 13)

• Compute what the next 14 bits of $y$ must be, using $y >> 14 = (B - y) \oplus x \oplus (x << 3) \oplus y$

• Compute what the next 14 bits of $x$ are, using $x = A - y$ (only this time, because we know 28 bits of $y$, we can reconstruct 28 bits of $x$)

• Compute what the next 28 bits of $y$ must be...

• Keep on doing this until we start predicting bits of $y$ above 63; because the right shift shifts in 0's, the prediction must be that they are all 0 (and if it predicts something else, we can reject the original guess of the lower 14 bits of $y$).

This involves iterating through 16384 different possibilities; a tad tedious by hand, but fairly trivial for a computer program...

I threw together a quick C routine to do the above search:

typedef unsigned long long num;
void solve_it(num a, num b) {
unsigned lower_14_y;

for (lower_14_y = 0; lower_14_y < (1<<14); lower_14_y++) {
    num y, x, upper_y = 0;
    int i;

    for (i=1;; i++) {
        y = (upper_y << 14) + lower_14_y;
        /* Lower i*14 bits of y are accurate */
        x = a - y;
        /* Lower i*14 bits of x are accurate */

        if (14*i >= 64) break;  /* Got all the bits */
        upper_y = (b - y) ^ x ^ (x << 3) ^ y;
    }

    if (b != y + (x ^ (x << 3) ^ y ^ (y>>14))) {
        continue;
    }
    printf( "Found solution %llx, %llx\n", x, y );
}
}

On my machine, it takes 80usec to run, and as kelalaka suspected, sometimes there aren't any solutions, and sometimes there are multiple (e.g. for a = 0x6c, b = 0xee, there are 7 solutions)