Re: solving equations with BitXor
- To: mathgroup at smc.vnet.net
- Subject: [mg107029] Re: solving equations with BitXor
- From: JH <jlucio at ubu.es>
- Date: Mon, 1 Feb 2010 06:10:34 -0500 (EST)
- References: <hk3ugn$drt$1@smc.vnet.net>
On 31 ene, 13:53, Jasper van Woudenberg
<jasper.van.woudenb... at gmail.com> wrote:
> Hi,
>
> I'm trying to have it solve a system of equations of the form (unknown_1
> xor ... xor unknown_n = known). These unknowns are 8-bit values, and
> therefore I'm representing them as BitXor[u1, .., un] = k1.
>
> However, I'm not getting very far. I would expect a simple
> Solve[BitXor[a,b]==c, b] gives me {b==BitXor[a,c]}, but instead I get
> something with an InverseFunction. How can I tell mathematica / Solve
> that BitXor[a,b]==c <-> BitXor[a,c]==b ?
>
> Cheers, Jasper.
_________________________________
Hello, Jasper:
I suggest Reduce, better than Solve (remember that Reduce looks for
ALL the solutions, and also allows you to specify domains and
conditions simultaneously).
For your problem, remember you have to take into account the integer
domain, and the range of your variables (between 0 and 255, as they
have 8 bits), so this is my suggestion:
For a simpler case where the 3 vbles are between 0 and 7, both
included, (i.e. they consist of only three bits), look the solutions:
Reduce[BitXor[a, b] == c && 0 <= a < 8 && 0 <= b < 8 && 0 <= c < 8, b,
Integers]
gives:
(a == 0 && c == 0 && b == 0) || (a == 0 && c == 1 &&
b == 1) || (a == 0 && c == 2 && b == 2) || (a == 0 && c == 3 &&
b == 3) || (a == 0 && c == 4 && b == 4) || (a == 0 && c == 5 &&
b == 5) || (a == 0 && c == 6 && b == 6) || (a == 0 && c == 7 &&
b == 7) || (a == 1 && c == 0 && b == 1) || (a == 1 && c == 1 &&
b == 0) || (a == 1 && c == 2 && b == 3) || (a == 1 && c == 3 &&
b == 2) || (a == 1 && c == 4 && b == 5) || (a == 1 && c == 5 &&
b == 4) || (a == 1 && c == 6 && b == 7) || (a == 1 && c == 7 &&
b == 6) || (a == 2 && c == 0 && b == 2) || (a == 2 && c == 1 &&
b == 3) || (a == 2 && c == 2 && b == 0) || (a == 2 && c == 3 &&
b == 1) || (a == 2 && c == 4 && b == 6) || (a == 2 && c == 5 &&
b == 7) || (a == 2 && c == 6 && b == 4) || (a == 2 && c == 7 &&
b == 5) || (a == 3 && c == 0 && b == 3) || (a == 3 && c == 1 &&
b == 2) || (a == 3 && c == 2 && b == 1) || (a == 3 && c == 3 &&
b == 0) || (a == 3 && c == 4 && b == 7) || (a == 3 && c == 5 &&
b == 6) || (a == 3 && c == 6 && b == 5) || (a == 3 && c == 7 &&
b == 4) || (a == 4 && c == 0 && b == 4) || (a == 4 && c == 1 &&
b == 5) || (a == 4 && c == 2 && b == 6) || (a == 4 && c == 3 &&
b == 7) || (a == 4 && c == 4 && b == 0) || (a == 4 && c == 5 &&
b == 1) || (a == 4 && c == 6 && b == 2) || (a == 4 && c == 7 &&
b == 3) || (a == 5 && c == 0 && b == 5) || (a == 5 && c == 1 &&
b == 4) || (a == 5 && c == 2 && b == 7) || (a == 5 && c == 3 &&
b == 6) || (a == 5 && c == 4 && b == 1) || (a == 5 && c == 5 &&
b == 0) || (a == 5 && c == 6 && b == 3) || (a == 5 && c == 7 &&
b == 2) || (a == 6 && c == 0 && b == 6) || (a == 6 && c == 1 &&
b == 7) || (a == 6 && c == 2 && b == 4) || (a == 6 && c == 3 &&
b == 5) || (a == 6 && c == 4 && b == 2) || (a == 6 && c == 5 &&
b == 3) || (a == 6 && c == 6 && b == 0) || (a == 6 && c == 7 &&
b == 1) || (a == 7 && c == 0 && b == 7) || (a == 7 && c == 1 &&
b == 6) || (a == 7 && c == 2 && b == 5) || (a == 7 && c == 3 &&
b == 4) || (a == 7 && c == 4 && b == 3) || (a == 7 && c == 5 &&
b == 2) || (a == 7 && c == 6 && b == 1) || (a == 7 && c == 7 &&
b == 0)
A less general example (a = 45 and c = 121):
Reduce[BitXor[45, b] == 121 && 0 <= b < 256, b, Integers]
gives:
b == 84
By the way, Mathematica only solves the last equation up to 10000 as
the maximum value for b (Why???).
Bye,
Jesus