6
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ Please improve your post using mathjax/LaTeX syntax $\endgroup$ – MrYouMath Sep 19 '15 at 13:58
  • $\begingroup$ sorry, hadnt had coffee yet, fixed (: $\endgroup$ – Alan Wolfe Sep 19 '15 at 13:59
  • 1
    $\begingroup$ Note that $f: x \pmod k \mapsto x \pmod 2$ is only a well-defined homomorphism if $2 \mid k$, and in this case $x \pmod 2 = f(x \pmod k)$ so there are no solutions, which means there's not much of a chance you can apply group/ring theory here. $\endgroup$ – Ricardo Buring Sep 20 '15 at 8:26
  • 1
    $\begingroup$ Do you want all solutions, or do you have any restrictions upon solutions? If you just want one (trivial) solution: for a fixed $x$ we want to find $k$'s such that $(x \% k)\%2 = 0$ and $(x\%k)\%2 = 1$, so we can just take $k = x$ and $k = x-1$. $\endgroup$ – Ricardo Buring Sep 20 '15 at 8:42
  • $\begingroup$ I just realized my notation was messed up. I migrated this from cryptography and lost the notation along the way. Fixed now! FWIW I'd prefer finding all solutions, but if there was a way to find a subset of solutions, or a numerical way to find solutions that was much, much, much faster than brute force, that would be acceptable too. My actual usage case that i'm working towards has many more x's and k's $\endgroup$ – Alan Wolfe Sep 20 '15 at 14:11
2
+100
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ intriguing! Thanks for this info arthur, very cool stuff. $\endgroup$ – Alan Wolfe Sep 24 '15 at 16:43
  • $\begingroup$ this only works if x and k are booleans, 0 or 1 right? i need integer solutions for the x's and k's unfortunately, 0 and 1 alone won't help me. really cool info though and very interesting :P $\endgroup$ – Alan Wolfe Sep 24 '15 at 22:10
  • 1
    $\begingroup$ This works for all integers. Under modulo mathematics if x = y mod m then x and y can be substituted for each other into polynomials and the same result is achieved in that modulo. if x = 2*c + 1 and y = 1 then $f(z) = a_n.z^n + ... + a_1.x + a_0$ mod 2 f(x) = f(y) mod 2 So you can solve the equations mod 2 then add multiples of 2 to any variable and it will still solve the equations. $\endgroup$ – arthur Sep 25 '15 at 0:30
0
$\begingroup$

I came up with a solution that I'm happy with so far, since it lets me find decent solutions that lets me move on with my reason for wanting to solve these equations.

I'm solving these equations:
$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$

I solve them by using the chinese remainder theorem for each $x_i$, and i use prime numbers for each $k_i$ value, where each $k_i$ gets it's own prime number. This is to ensure than the $k_i$ values are co-prime, when running them through the chinese remainder theorem algorithm.

This works well and answers are calculated extremely fast, so I'm happy :P

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.