Solving equation of xor and mod operation

How do I solve equations like this $$(aX \oplus X+b) \bmod M = c$$

If a,b and c are known?
and if i have system of of equation with different b values, is it solvable? I am particularly interested in $$M$$ being a power of $$2.$$

• It's easy if $M$ is a power of 2. I assume it's not... Oct 4, 2023 at 19:06
• lets say m = 2**128
– Sora
Oct 4, 2023 at 20:49

is it solvable?

If $$M$$ is a power of 2, say, $$2^{128}$$, then it is easily solvable.

We first recognize that, in this system, what happens to bits $$0-k$$ are not affected by any of the bits $$k+1$$ and above. That is, we can solve the system to the modulus $$2^k$$ and then extend that answer to higher order bits.

To be more concrete, here is what we can do:

• Define the set of the solutions modulo $$2^0$$; this set consists of a single entry $$X = 0$$, because for any integers $$x, y$$, $$x \equiv y \pmod 1$$

• For $$k=1$$ up to $$128$$ we consider the set of solutions modulo $$2^{k-1}$$

• For each such solution, we extend $$X$$ by setting bit $$k-1$$ to 0, and see if that's a solution. If it is, we add that to the set of solutions modulo $$2^k$$.

• Then, we extend $$X$$ by setting bit $$k-1$$ to 1, and see if that's a solution. If it is, we add that to the set of solutions modulo $$2^k$$

After we reached $$k=128$$, the final set will have all the solutions modulo $$2^{128}$$

And, yes, this process is fast

• Yes. That tends to be applicable to solve for $X$ many equations $f(X)=0$ where $f$ has no right-diffusion (and $f$ does not collide too much, especially if we want all the solutions). Here, depending on how we read the question, $f(X)=((((aX)\oplus X)+b)\bmod2^b)\oplus c$, or $f(X)=(((aX)\oplus(X+b))\bmod2^b)\oplus c$ (with $b=128$).
– fgrieu
Oct 5, 2023 at 5:48