2
$\begingroup$

I have a system of equations. This system is 8 equations for 16 unknowns. Is it possible to solve the equations for some answer? By that, I mean, it's highly likely that they will have several possible answers, but I only need one. I have only ever covered solving simultaneous equations for exact answers where the number of equations is equal to the number of variables.

All of the equations probably involve all of the unknowns. But since each one is 15MB to express, I didn't check.

As an aside, the equations are guaranteed to contain only relatively simple operations, specifically, addition (modulo 2^32), binary rotation (by constant only), right shift (by constant only), exclusive or, negation, and binary AND. No squares or exponentials or anything like that.

Edit: We are talking about something like this. But bigger. A lot bigger. Where h[7] means that this corresponds to the 8th input, and c[i] corresponds to the ith output. I reduced the complexity a lot, so it's more digestible. The real thing is a lot bigger. And there's 8 of them.

Edit: I eventually determined that the reason the final equations are so large is because there are many, many intermediate variables. If expressed as these variables, then it becomes much more managable- the whole kaboodle in only 64kb, and shown here.

Now, given h[0] - h[7], I definitively solved for 113 of the 2271 states. However, going further than that gave me problems- there are so many states that I can't identify any simultaneous equations to attempt to solve, or any other method of proceeding.

I identified 24 equations where one term is known (one of the 113) and the other two are unknown variables. Is this the part where I start adding in information?

  • 0
    What kind of equations? Linear equations? Polynomial equations? If they are linear equations, then there is a standard method to generate *all* solutions: Gaussian elimination.2012-05-17
  • 0
    @Arturo: I'm not *entirely* familiar with the kinds of equation, but they are not polynomial in that the only power any variable is raised to is 1. I *think* it's non-linear, the Wiki page only ever suggests multiplication and addition, whereas I have addition and a bunch of binary operations.2012-05-17
  • 0
    A "linear equation" is one of the form $a_1x_1+a_2x_2+\cdots+a_nx_n=c$, where $x_1,\ldots,x_n$ are the unknowns, and $a_1,\ldots,a_n,c$ are constants. What kind of operations do you have?2012-05-17
  • 0
    @Arturo: I listed them at the bottom of the question. Only addition and binary rotation, shift, xor, and negation. Not even multiplication (although arguably, a shift could be expressed as a multiplication).2012-05-17
  • 0
    @DeadMG If you suspect, that you might get more than one solution i.e. if you have degrees of freedom, you can set some of the variables to take some specific value so that you can find 'a' solution to your problem.2012-05-17
  • 0
    @Marvis: I've been thinking about that. The problem is that although there are many, many solutions to be expected, the solution space is so vast that there is little hope of achieving an output in such a fashion.2012-05-17
  • 0
    @DeadMG Could you give an example of the equations you are dealing, say for instance $3$ equations and $6$ unknowns?2012-05-17
  • 0
    @Marvis: I actually don't know how to reduce the complexity that way. The original function (which this is supposedly the inverse of) has some extremely stringent specifications and I would likely just break it by trying to alter it. I did however post the equation for the eighth input on a much, much reduced complexity version.2012-05-17
  • 0
    Would it be right to say that you have equations for eight $h[i]$ in terms of eight $c[i]$, and you want to invert the system so that you have an equation for each of the $c[i]$ in terms of the $h[i]$?2012-05-17
  • 0
    @MarkBennet: There are sixteen `c[i]`, rather than 8. But yes, that would be correct. Or rather, I would be fairly satisfied with simply knowing that it is actually possible.2012-05-17
  • 0
    Take the red pill: http://en.wikipedia.org/wiki/Algebraic_geometry2012-05-19
  • 0
    Where are your equations coming from? Is there any chance they're equivalent to a system of equations involving basic math operations (addition, multiplication, exponentiation) and not "computer science" operators like XOR, bit rotation, etc? In their current form, your equations are horribly non-smooth and so the standard, powerful optimization tools can't be put to use on them.2012-06-25

1 Answers 1