Solving Unknown Variables in F(x): Friend vs Me Debate

[CyberStasi]

On a recent outing with friends we came up on a debate and I am hoping someone can help me find out who was right. The discussion was on whether one could create an equation where in you have 2 unknown variables and any number of known variables and the solution, that will allow you to solve for the 2 unknown variables.
For the issue at hand we had agreed on the following details.

1) All variables must be between Hex values (0-F). (we decided to keep it simple)
2) You must use some form of reduction in size so that your answer is the same number of characters as your input. (whether you ditch the higher values or mathmaticaly reduce them is up to you) IE if you use 4 hex values for each variable, your answer must not be greater than 4 hex values. (binary reduction is easy to do: If there are overflow bits, just XOR with a known value to reduce - which is fully reversable so you arent loosing any information)
3) You must have 2 unknown variables.
4) You may have any number of known variables in your function. You can choose 3, 5, 42, etc.
5) You may use any math you wish, as long as you adhear to rule 2 for the function solution.
6) You must be able to solve using only one function.
7) You are allowed to generate lookup tables to help you solve if you need.
8) You must be able to provide examples of how your function is solveable in reverse.


He agrued that you could create a single function that when a person knows the solution and all but 2 variables, they can compute the two missing variables. The matter isn't if this is easy to do computationaly, but if it is possible. His possible solution was to use something like the CRC16 or any of the CRC hashes or a one way hash function from something like RSA. Now due to the computational complexity of using RSA, he suggested using a system of only 4 bytes of data instead of the full 64bytes. But his argument was that you could create a function (algorithm) where in you could know all but two of the variables and be able to calculate their exact value, and that you wouldn't have the problem of collisions. (More than one possible pair of values that would give you the known answer). For example, take the equation ((((A/B) * C) / D) * E) = F. If you know F and can choose to know any 3 variables from A, B, C, D, E. Could you solve the for the other 2 without having another equation at your disposal.

My stance was that you would need 2 solutions to be able to solve for either unknown variable. I Do not believe that calculating every possible value of those two unknown variables would enable you to prove the exact values, as without anything to use as a referance (another known solution); you would end with with 2 or more possible answers for those variables and would not be able to determine which of them was correct.

However since we are keeping the variable size small, and we are allowed to use lookup tables; it may be possible to create a function that this is possible to do, simply by brute forcing all possible values for your two unknown variables. But would this give you only one result per function solution (Variable F) or would you be left with collisions?


As a last question before we split up for the night the challange was altered. Same basic rules except this time you have 3 unknown variables and any number of known; but you have 2 known functions each with their own known answer. Would this be possible as well? (this will be the discussion when we get together again.)

 

[epkid08]

Can an elementary function be constructed so that it has a domain restricted to a single constant? If the function was of one of the unknown variables, then that unknown variable would be restricted to some constant value, regardless of the other unknown variable.

 

[CyberStasi]

Can an elementary function be constructed so that it has a domain restricted to a single constant? If the function was of one of the unknown variables, then that unknown variable would be restricted to some constant value, regardless of the other unknown variable.

In the debate my friend and I were having, the function would be a known. In simple algabraic terms. F(x) = x+y=Z. If Y and Z are known you can solve for X. The debate was whether you could create a single function, that while knowing the function structure and knowing Z you would know all but 2 of the variables. IE a+b+c+d+e=F. Obviously that won't work because if c=1, d=2, e=3, and F=15. You could solve to a + b = 9. But you have no way to tell which between a and b is 4 and which is 5.
The only way that I can see it possibly working out is if one of the known variables, let's say c, acts upon one of the unknown in a way that would thus give you a solution that could not be reached of the values of a or b were mixed. Say a/c + b/d + e = F. In that function the values for a and b cannot be interchanged. However in that function you there could be mutiple values for a and b that would work. Example: a=2 b=8 c=4 d=16 e=1. In that case F would equal 2. However if the value of a=1 and the value of b=12, F would still equal 2.
I run into either problem: not being able to tell what is a or b, or being able to distinguish them apart but not knowing which possible solution they are.

 

[matt grime]

IE if you use 4 hex values for each variable, your answer must not be greater than 4 hex values. (binary reduction is easy to do: If there are overflow bits, just XOR with a known value to reduce - which is fully reversable so you arent loosing any information)

Why would XORing in something make it 'reduced'? Normally AND is used for 'reduction' but that isn't reversible. I agree XOR in a constant and you don't 'lose' information, but that won't get you something inside a certain range.

Moreover, you have a function in two variables, say in the range [0,255] each, and you want the answer to be in the range [0-255], well, that cannot be injective so no, you can't make things invertible.

 

[CyberStasi]

Why would XORing in something make it 'reduced'? Normally AND is used for 'reduction' but that isn't reversible. I agree XOR in a constant and you don't 'lose' information, but that won't get you something inside a certain range.

Moreover, you have a function in two variables, say in the range [0,255] each, and you want the answer to be in the range [0-255], well, that cannot be injective so no, you can't make things invertible.

In my other quote I reference one of the functions of the AES algorithm. https://www.physicsforums.com/showthread.php?t=314497".
In that example, when you are doing your multipilcation you will overflow in Step 2.

For example, {57} · {13} = {fe} because
{57} · {02} = xtime({57}) = {ae}
{57} · {04} = xtime({ae}) = {47}
{57} · {08} = xtime({47}) = {8e}
{57} · {10} = xtime({8e}) = {07},
thus,
{57} · {13} = {57} · ({01} XOR {02} XOR {10})
= {57} XOR {ae} XOR {07}
= {fe}.

At Step 2 you will overflow as {ae} · {02) = 15c. It is reduced back to within the range of [0-255] by XOR of 11b. {15c} XOR {11b} = {47}. As I am sure you know, you can simply revert this back by doing the reverse. {47} XOR {11b} = {15c}.
(In case someone doesn't understand why I multiplied by 02 there instead of 04, I already multiplied by 02 in the previous step, so to multiple 57 by 04 just means I take 57x02 and multiple it by 02. 02x02=04)

Something like this will reduce your value back down to an acceptable range. As long as you know the Constant you are XORing with, you are able to back step it. The only issue I see is how would you know whether you would need to backstep it or not. IE is 47 a reduced answer or an answer on its own.

Overall there is no worry of overflow throughout the function, it was simply that the output length be the same as the input length. But as I said, I believe this creates the problem of having an answer that you are unware of whether it is 'reduced' or not. Effectively rending the problem unsolvable.

 

[matt grime]

Something like this will reduce your value back down to an acceptable range. As long as you know the Constant you are XORing with, you are able to back step it.

You're focussed on the wrong thing entirely - you're just applying an affine transformation. It is not the representation of your image that is the problem. It is just that you're defining a function from XxX to X (where X is whatever finite set you care about) and this is never left invertible. It would be elementary to do this with real numbers, or any infinite set for that matter, for example X=N the natural numbers (m,n)--> 2^m3^n will do.

 

[CRGreathouse]

He agrued that you could create a single function that when a person knows the solution and all but 2 variables, they can compute the two missing variables. The matter isn't if this is easy to do computationaly, but if it is possible.

If the unknowns m and n are integers and the function f is given, then there's a trivial algorithm to find a pair (m, n) that gives f(m, n) = k if such a pair exists:

for (t in {0, 1, 2, ...})
  for (m in {0, 1, ..., t})
    for (n in {0, 1, ..., t})
      if (f(m, n) = k)
        return (m, n)
      if (f(m, -n) = k)
        return (m, -n)
      if (f(-m, n) = k)
        return (-m, n)
      if (f(-m, -n) = k)
        return (-m, -n)

If the unknowns x and y are real numbers and the function f is given by a closed-form expression involving only real constants, +, -, *, and /, by a theorem of Tarski you can find a pair (x, y), or show that none exists, such that f(x, y) = k.

If the unknowns x and y are real numbers and the function f is given by a closed-form expression involving only real constants, +, -, *, ^, sin, and abs, by a theorem of Richardson your friend can design some function so complicated that you won't be able to find (x, y) or to show that none exists, such that f(x, y) = k.

 

[CRGreathouse]

Can an elementary function be constructed so that it has a domain restricted to a single constant?

I think you're looking for something like
$$f(x) = \sqrt{-(x - k)^2}$$
which for $f:\mathbb{R}\Rightarrow\mathbb{R}$ allows only k in the domain. (But usually the domain is a part of the function definition itself, so the question would be trivial.)