Why Is This Game Hard?

In the previous post we introduced the Integer Factorization game and also provided a JavaScript implementation so that you can actually play it online. We made the claim that this game is as hard as factorizing integers. In this post we'll show why this is the case and also show how to build hard to solve initial positions.

Each position encodes a (move invariant) number

Recall that the goal of the game is to reach a final position from an initial one by moving tokens on the top-left bottom-right diagonals (the "blue" moves) or duplicating them on the next-higher diagonal (the "red" moves). For a given position let's assign numbers to all diagonals as shown in the following image:

and then compute the "number" for this position by assigning to each token the value of its top-left bottom-right diagonal and then summing all token values. For example the above position's number is 1 + 4 + 8 + 64 = 77. It should be clear that moving a token on the same top-left bottom-right diagonal (the "blue" move) will not change this value. The "red" move maintains this number, too. For example, replacing the token on the diagonal "8" with two new tokens on the "4" diagonal will keep the invariant: 1 + 4 + 4 + 4 + 64 = 77.

The connection with the binary multiplication

In the following image you could actually see an initial and a final position that have the same invariant number:
1 + 4 + 8 + 64 = 1 + 2 * 2 + 2 * 4 + 2 * 8 + 16 + 32 = 77.

⇒⇒⇒

You might also observe that 77 = 11 * 7 and this equality in binary is 1001101 = 1011 * 111. If we shift the rows to left until diagonals become columns, as shown in the following image

should be relatively easy to see that the tokens in the final position are actually depicting the  1011 * 111  binary multiplication method taught in school:

   1011
  x 111
  -----
   1011
  1011
 1011
-------
1001101

The conclusion

Based on the above observations we figure out that solving a game position is equivalent to factorizing the corresponding position's number. What we actually do when playing the game is the reverse of the binary multiplication method taught in school: we start with a position encoding a number in binary, for example 1001101, and we try to move or duplicate the tokens to arrive to a position representing some binary multiplication, for example 1011 * 111.

Hard initial game positions

Obviously the game as implemented here is not that difficult to solve as we cannot have initial positions encoding numbers larger than 2¹⁵ - 1. Solving positions on larger boards is a different problem though. At the time of writing there is a $200,000 cash prize for factorizing this RSA-2048 number:

RSA-2048 = 2519590847565789349402718324004839857142928212620403202777713783604366202070
           7595556264018525880784406918290641249515082189298559149176184502808489120072
           8449926873928072877767359714183472702618963750149718246911650776133798590957
           0009733045974880842840179742910064245869181719511874612151517265463228221686
           9987549182422433637259085141865462043576798423387184774447920739934236584823
           8242811981638150106748104516603773060562016196762561338441436038339044149526
           3443219011465754445417842402092461651572335077870774981712577246796292638635
           6373289912154831438167899885040445364023527381951378636564391212010397122822
           120720357.

We can encode this number as an initial game position by using a chess board of size 1025 and, based on the fact no one managed to factorize RSA-2048 yet, this game position should be hard to solve.
But why is integer factorization a hard problem? We will discuss this topic in our next post.