Solving the "Black Box" Puzzle with Math Lovers

[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) = ( a₀ + a₁*x¹ + ... + a₇*x⁷ ) 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₀ + a₁x + a₂x²

a₀ = 3
a₁ = 7
a₂ = 2

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

a₀ + a₁ + a₂ = 12
a₀ + 2a₁ + 4a₂ = 25
a₀ + 3a₁ +9a₂ = 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₀ + a₁ + a₂ = 12
a₀ + 2a₁ + 4a₂ = 12
a₀ + 3a₁ +9a₂ = 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

 

[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.

 

[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?

 

[Live2Learn]

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

1) Express p(x_i) mod M = y_i as

p(x_i) - (n_i)M = y_i

where n_i 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(x_i) - n_iM = y

and p(x_j) - n_jM = y where x_i \neq x_j

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, n_iM, 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.

 

[SBaldrick]

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

 

[SBaldrick]

ah rotation matrix! good

 

[SBaldrick]

still i don't 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.

 

[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.
In your simplified case:

F(x) = ( a₀ + a₁x + a₂x² ) MOD M = y

form the system:

a₀ + a₁x_i + a₂x_i² + a₃x_i³ + a₄x_i⁴ + a₅x_i⁵ = y_i

you will need 6 of these equations.

When you have solved for the coefficients form the set:

[ a₃x_i³ + a₄x_i⁴ + a₅x_i⁵ ]

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

 

[luma]

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