I am very new to algebra with bitwise operators.
If i have 5x ^ 7x ^ 9x = 22
is it possible for me to solve for x (if so how is it done)? Do normal algebra techniques hold (factoring out x etc.?)
I know that if x = 2, then the above equation is true
((5 * 2) ^ (7 * 2) ^ (9 * 2)) = (10 ^ 14 ^ 18) = 22 (where, * is normal multiplication)
Thanks.
I think this is possible for equations of the form:
$${\bigwedge}(a_ix+b_i)=C$$
(Here I just used $\wedge$ for bitwise xor.)
We will compute $x \pmod{2^m}$, increasing $m$ slowly. This method tries to reduce the "branching factor" when solutions are computed, not all numbers from $0$ to $2^m-1$ are necessarily tested. It's still not very efficient, and I'm yet to find a terminating condition other than "go large enough".
Let $m=1$. Then consider the parity of all the terms. Without further information, we can compute the parity of the left-hand side and the right-hand side. There are $3$ possibilities, either both $0, 1$ work, one of $0, 1$ work, or none of them work (which means no solution).
As we are only interested in finding roots, maybe there is really more than $1$ root. For example, $(3x)^\wedge(3x)=0$ has infinitely many solutions.
Suppose we know that a possible root $r$ satisfies $r\equiv n\pmod{2^m}$, so we want to be able to find the possible values of $r \pmod{2^{m+1}}$.
We take the entire equation $\pmod{2^{m+1}}$, and substitute the $2$ possible values of $r$, which are $r, r+2^m\pmod{2^{m+1}}$.
Let's use your example:
$(5x)^\wedge(7x)^\wedge(9x)=22$
Taking $\pmod2$, we obtain $x^\wedge x^\wedge x\equiv0$, so $x\equiv0\pmod2$
Taking $\pmod4$, we obtain $x^\wedge(3x)^\wedge x\equiv2$. This simplifies to $3x\equiv2$, so $x\equiv2\pmod4$.
Taking $\pmod8$, we obtain $(5x)^\wedge(7x)^\wedge x\equiv6$. Substituting $x\equiv2,6\pmod8$, we get that $2$ works, and $6$ does not.
Taking $\pmod{16}$, we obtain $(5x)^\wedge(7x)^\wedge(9x)\equiv6$. Substituting $x\equiv2,10\pmod{16}$, we get that both $2$ and $10$ work.
Taking $\pmod{32}$, we obtain $(5x)^\wedge(7x)^\wedge(9x)\equiv22$. Substituting $x\equiv2,10,18,26\pmod{32}$, we get that only $2$ works.