Hello, my name is Eugene, i am glad i found a forum for people who love math.(adsbygoogle = window.adsbygoogle || []).push({});

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) = ( a_{0 }+ a_{1}*x^{1}+ ... + a_{7}*x^{7}) MOD M

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

the goal is to find out all a_{i}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) = a_{0}+ a_{1}x + a_{2}x^{2}

a_{0}= 3

a_{1}= 7

a_{2}= 2

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

a_{0}+ a_{1}+ a_{2}= 12

a_{0}+ 2a_{1}+ 4a_{2}= 25

a_{0 }+ 3a_{1}+9a_{2}= 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 -

a_{0}+ a_{1}+ a_{2}= 12

a_{0}+ 2a_{1}+ 4a_{2}= 12

a_{0 }+ 3a_{1}+9a_{2}= 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

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Black box!

Loading...

Similar Threads - Black | Date |
---|---|

Algebra is like a black box? | Mar 6, 2009 |

**Physics Forums - The Fusion of Science and Community**