# Black box!

1. May 6, 2010

### SBaldrick

Hello, my name is Eugene, i am glad i found a forum for people who love math.

I was reading a book on mathematical puzzles recently, and there was one which i couldn't solve, mostly because i am not a very clever guy. Perhaps you will have some ideas?

The area of the puzzle is non -linear algebra and number theory.

The author talks about a following situation. We have a machine, which can accept input (an integer) , and produce an output (also an integer) depending on the input.
We know, that calculations inside the machine are following:

F(x) = ( a0 + a1*x1 + ... + a7*x7 ) MOD M

But we don't know modulo or coefficients. However, M, ai, x must be between [0, 65535]

the goal is to find out all ai coefficients and modulo M;

We can calculate F function arbitrary number of times for any argument we want .

---------------------------------------------------------------------------------------------
Now, my ideas so far were:
1) We can build a system of linear equaions (8 of them), for x between 0 to 7, and solve it with Gaussian reduction, or with Kramer rule. This would give us all coefficients easily.
For instance (slightly shorter example)

let the inner state of the machine be: F(x) = a0 + a1x + a2x2

a0 = 3
a1 = 7
a2 = 2

then F(1) = 12, F(2) = 25, F(3) = 42 and the system of equations is:

a0 + a1 + a2 = 12
a0 + 2a1 + 4a2 = 25
a0 + 3a1 +9a2 = 42

and by applying the Kramer rule we get the correct values of coefficients, 3, 7 and 2.

But we have a problem - modulo M.

Now if M is a prime (13 for simplicity) : the system changes -

a0 + a1 + a2 = 12
a0 + 2a1 + 4a2 = 12
a0 + 3a1 +9a2 = 3

And the results would be 3, 13.5 and -4.5
Result is in the same class modulo M as the original coefficients, and we can obtain original:

13.5 = 27/2 (mod 13) = (27 + 13) / 2 = 40/2 = 20 (mod 13) = 7

in the same way:

-4.5 = -9/2 ( mod 13) = (-9 + 13) /2 = 4/2 =2

And we can find inside state of function F. This however, needs the modulo to be known.

But if the modulo M is not prime (say 14), for the system above results would be:
3, 14, -5 or after doing the modulo operation : 3, 0, 9

Now, the answer is not correct (the inside state of F function are different).

So, i am having trouble with this bit.

I understand, that if we calculate all possible results for all 60 + thousand inputs, we will have a table with which we can recreate the F function.

But the author states that there is a more brilliant solution, which requires lesser amount of computations.

Do you find it interesting? Perhaps you would also like to know the answer? The author calls this puzzle a "black box"

Lets try solving it together!

regards, S. Baldrick

2. May 7, 2010

### TMM

Fascinating problem.

f(0),f(1),...,f(7) gives a system of 8 equations mod M. They seem to be linearly independent, but I haven't checked. If so, these can be diagonalized to give solutions to the coefficents of f mod M. Then we just need a way of finding the modulus.

3. May 8, 2010

### SBaldrick

TMM, thanks for participation.

Now, the only way to find modulus which i spotted is following:
function F can be substituted by an integer number, which is its result. Therefore the F function is equal to simply (integer mod M) and the result will be numbers from 0 to M-1, like if M is 13, we will have either 0, 1, 2, blah blah up to 12 as the result. And there will be exactly M classes modulo M, so we can find modulus by calculating all possible arguments x in F(x) and calculating the number of classes or do just a part of calculations and find the largest residue modulo M, which will be the M-1 with certain probability depending on the amount of calculations.

the F(x) function looks like Fourier transform in GF, and knowing M we can find coefficients by means of inverse fourier transform, but again, modulus must be prime, else the situation is dubious.

also i think we can use Lagrange formula to interpolate the polinimial.

Any ideas, sirs?

4. May 12, 2010

### Live2Learn

Here are some thoughts about one possible way to approach this problem.

1) Express p(xi) mod M = yi as

p(xi) - (ni)M = yi

where ni is an integer

2) Set up a system of equations. Note you will have 2 more variables than equations. To reduce the number of variables you can use 2 pairs of data points that have the same y value.

Example: p(xi) - niM = y

and p(xj) - njM = y where xi $$\neq$$ xj

Setting these 2 equations equal to each other, you should be able to express one of the varibles in terms of the others, thus, by doing this for 2 pairs of data points, your system should have an equal number of equations and variables.

3) express the cross products, niM, as a sum of squares by rotating the axis 45 degrees.

4) Solve the resulting linear system and rotate back.

I havn't verified that this is correct yet, nor do I think it is the most elegant solution. There may also be some flaw, missing step(s), or technical dificulty I don't see yet! Anyways, here is my stab at it.

Last edited: May 12, 2010
5. May 19, 2010

### SBaldrick

oh grand! sorry, but i don't quite follow what "rotate the axis" means mathematically.
a small example, somebody?

6. May 19, 2010

### SBaldrick

ah rotation matrix! good

7. May 19, 2010

### SBaldrick

still i dont see how finding a collision caused by two data points (which are congruential no doubt) will help.
we will still have unknown M and two different ni and nj.

8. May 19, 2010

### Live2Learn

My original atempt to solve this puzzle won't work because I still can't form an independent set of equations without having information about the coefficents. However, I've come up with another (half-baked) idea.

F(x) = ( a0 + a1x + a2x2 ) MOD M = y

form the system:

a0 + a1xi + a2xi2 + a3xi3 + a4xi4 + a5xi5 = yi

you will need 6 of these equations.

When you have solved for the coefficients form the set:

[ a3xi3 + a4xi4 + a5xi5 ]

M should be a common factor in this set ( if all goes well ).

9. May 24, 2010

### luma

brute force the values in python. it can easily do this in a few seconds for whatever output you want.