Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Black box!

  1. May 6, 2010 #1
    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. jcsd
  3. May 7, 2010 #2

    TMM

    User Avatar

    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.
     
  4. May 8, 2010 #3
    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?
     
  5. May 12, 2010 #4
    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 [tex]\neq[/tex] 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.:smile:
     
    Last edited: May 12, 2010
  6. May 19, 2010 #5
    oh grand! sorry, but i don't quite follow what "rotate the axis" means mathematically.
    a small example, somebody?
     
  7. May 19, 2010 #6
    ah rotation matrix! good
     
  8. May 19, 2010 #7
    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.
     
  9. May 19, 2010 #8
    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:redface:. However, I've come up with another (half-baked) idea.
    In your simplified case:

    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:confused: ).
     
  10. May 24, 2010 #9
    brute force the values in python. it can easily do this in a few seconds for whatever output you want.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook