Hello,

I always thought about asm community as the best forum. Now, though a question i ask is not directly connected with assembly or indeed computers in general, i still hope that readers, being in possesion of a keen brain, would provide as much help as they can.

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!

Posted on 2010-05-06 14:16:13 by Turnip
Hello, some comments from me.

You are right that the question is trivial when M is a prime as it forms a field of characteristic M and so for every element in M (except the 0 element) there is an inverse element (which can be calculated using fermat's littler theorem or euclid's algorithm). Hence, we can perform Guassian Elimination and solve the thing (I've solved such a problem before and coded it out).

Now the main thing is when M is not a prime. I'm not too sure how to continue from there. Will think about it more when I have time.
Posted on 2010-05-26 18:53:18 by roticv
Hello
great somebody showed interest at last. I've asked around concerning non-prime modulo and usually people mentioned that theory concerning such equations is too complex and not very advanced yet.

still i don't know much about whether its so.

Posted on 2010-05-30 08:14:48 by Turnip