Cómo resolver ecuaciones simultáneas de módulo / diofánticas

Question

¿Alguien sabe cómo resolver un conjunto de ecuaciones como éste?

$(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$

Estoy tratando de encontrar valores válidos de $x_i$ y $k_i$ . He encontrado algunas soluciones utilizando un programa de fuerza bruta, pero quiero subir el número de $x$ 's, $k$ lo que descarta la fuerza bruta como solución práctica.

Por ejemplo, hay dos $x$ valores anteriores, que se traducen en $2^x$ $k$ valores, y $x2^x$ ecuaciones. Me gustaría tomar el número de $x$ valores hasta 16, o 32 si es posible, lo que resulta en un número enorme de $k$ y ecuaciones.

¿Alguien puede ayudar en algo, incluso para indicarme alguna dirección?

Conozco el teorema del resto chino, la inversa modular multiplicativa y el algoritmo euclidiano extendido, entre otras técnicas matemáticas básicas del módulo, pero no estoy muy seguro de cómo avanzar en esto.

Gracias.

Editar: Para aclarar un poco, Idealmente me gustaría encontrar todas las soluciones a este problema, pero si hay una manera de encontrar un subconjunto de soluciones, como si las ecuaciones de abajo se puede resolver que estaría bien también. O, si hay alguna manera de encontrar soluciones numéricamente que es mucho más rápido que la fuerza bruta permutando el $x_i$ y $k_i$ y comprobar si se ajustan a las restricciones, eso también sería útil.

$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$

Answer 1

Si hay un gran número de soluciones, cualquier método para reducir su búsqueda seguirá teniendo muchas variables indeterminadas.

Dicho esto, algunas ecuaciones de módulo 2 pueden reducirse a ecuaciones exclusivas o (xor) que tienen métodos de reducción similares a los de las ecuaciones lineales.

(x%k)%2 = r puede escribirse como $x + ck \equiv r \pmod2$ que puede escribirse como la ecuación lógica $$x\oplus ck \oplus r = 0$$ donde $\oplus$ es el operador xor y x,c,k,r son valores booleanos.

Por ejemplo, si r = 0 entonces $x=ck$ . Si r = 1 entonces $x=ck\oplus 1$ , $x= not\ ck$ .

Puedes convertir todas las ecuaciones mod 2 en ecuaciones xor y luego reducirlas a una forma triangular superior Uz = b, z = [x ck]'. Si no hay soluciones, la línea inferior no nula será 0 = 1. Si hay una solución única, la línea inferior tendrá la forma $z_t$ = [0|1]. Si hay varias soluciones entonces será de la forma $z_1\oplus z_2\oplus z_3\dots=[0|1]$ . Tendrás que probar las combinaciones que resuelven la ecuación y subir la matriz U haciendo lo mismo con esas ecuaciones.

Los términos ck aumentan el número de soluciones. Si ck = 1 entonces (c=1,k=1). Si ck = 0 entonces (c=0,k=0) o (c=0,k=1) o (c=1,k=0).

Answer 2

Llegué a una solución con la que estoy contento hasta ahora, ya que me permite encontrar soluciones decentes que me permiten seguir adelante con mi razón de querer resolver estas ecuaciones.

Estoy resolviendo estas ecuaciones:
$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$

Los resuelvo utilizando el teorema del resto chino para cada $x_i$ y utilizo números primos para cada uno $k_i$ donde cada $k_i$ tiene su propio número primo. Esto es para asegurar que el $k_i$ son coprimos, al pasarlos por el algoritmo del teorema del resto chino.

Esto funciona bien y las respuestas se calculan extremadamente rápido, así que estoy contento :P