Does anyone know how i'd solve a set of equations like this?
$(x_0\%k_0)\%2=0$
$(x_0\%k_1)\%2=1$
$(x_0\%k_2)\%2=0$
$(x_0\%k_3)\%2=1$
$(x_1\%k_0)\%2=0$
$(x_1\%k_1)\%2=0$
$(x_1\%k_2)\%2=1$
$(x_1\%k_3)\%2=1$
I'm trying to find valid values of $x_i$ and $k_i$. I've found some solutions using a program to brute force it, but I want to up the number of $x$'s, $k$'s which rules out brute force as a practical solution.
For instance, there are two $x$ values above, which translate to $2^x$ $k$ values, and $x∗2^x$ equations. I'd like to take the number of $x$ values up to 16, or 32 if possible, which results in huge numbers of $k$'s and equations.
Anyone able to help at all, even to point me in some direction?
I do know about the chinese remainder theorem, multiplicative modular inverse and the extended euclidean algorithm, among some other basic modulus math techniques, but I'm not really sure how to make any progress on this.
Thanks!
Edit: To clarify a bit, Ideally I'd like to find all solutions to this problem, but if there is a way to find a subset of solutions, like if the equations below could be solved that would be fine too. Or, if there is some way to find solutions numerically which is much faster than brute force permuting the $x_i$ and $k_i$ values and testing if they fit the constraints, that'd be helpful too.
$x_0\%k_0=0$
$x_0\%k_1=1$
$x_0\%k_2=0$
$x_0\%k_3=1$
$x_1\%k_0=0$
$x_1\%k_1=0$
$x_1\%k_2=1$
$x_1\%k_3=1$
If there are a large number of solutions then any method of reducing your search will still have many indeterminate variables.
That said some modulo 2 equations can be reduced to exclusive or (xor) equations that have similar reduction methods to linear equations.
(x%k)%2 = r can be written as $x + ck \equiv r \pmod2$ which can be written as the logic equation $$x\oplus ck \oplus r = 0$$ where $\oplus$ is the xor operator and x,c,k,r are Boolean values.
e.g. If r = 0 then $x=ck$. If r = 1 then $x=ck\oplus 1$, $x= not\ ck$.
You can convert all of the mod 2 equations into xor equations then reduce them into an upper triangular form Uz = b, z = [x ck]'. If there are no solutions then the bottom non zero line will be 0 = 1. If there is a unique solution the bottom line will have the form $z_t$ = [0|1]. If there are multiple solutions then it will be of the form $z_1\oplus z_2\oplus z_3\dots=[0|1]$. You will have to try the combinations that solve the equation and move up the U matrix doing the same with those equations.
The ck terms increase the number of solutions. If ck = 1 then (c=1,k=1). If ck = 0 then (c=0,k=0) or (c=0,k=1) or (c=1,k=0).