E-Casino

A pseudo random number generator (PRNG) is a program that takes an input called a seed and outputs a sequence of random bits $r[0], r[1], \dots$, where every bit is 0 or 1.

Fix one PRNG and one seed. A gambler is a person (or a computer) who has observed the first $L$ output bits $r[0], r[1], \dots, r[L-1]$. The gambler knows the algorithm of that PRNG and therefore knows how the bits are produced. The seed is the only secret. From the algorithm and the observed prefix, the gambler wants to predict the bits that come next, $r[L], r[L+1], \dots$.

Designing a PRNG that resists this is not easy. The company E-Casino uses the following method. By observing some natural phenomenon, the company first produced a long sequence of $N$ random bits $S[0], S[1], \dots, S[N-1]$. The array $S$ is public, so gamblers can read it too. The seed is a pair $(k, m)$ made of an integer $k$ with $0 \le k < N$ and an $M$-bit sequence $m = \langle m[0], m[1], \dots, m[M-1] \rangle$. For $j = 0, 1, 2, \dots$ the output bit $r[j]$ is

$r[j] = S[(k + j) \bmod N] \oplus m[j \bmod M]$

where $\oplus$ is the exclusive or operation: for bits $a$ and $b$, $a \oplus b = (a + b) \bmod 2$.

The company always uses $N = 2048$ and $M = 32$. Every morning the managers of E-Casino meet and pick the secret seed $(k, m)$ that generates the sequence for that day.

You are the gambler. On one particular day you have observed the first $2M = 64$ output bits $r[0], r[1], \dots, r[63]$, and you also know the array $S$. You do not know $k$ or $m$. Recovering the later bits starts with recovering $k$, so that is the job here. Find the smallest $k$ that agrees with the bits you observed.

The input is a single line. Its first $2M$ characters are the observed bits $r[0], r[1], \dots, r[2M-1]$, each written as 0 or 1, the very first character being $r[0]$ and the next one $r[1]$. One % character follows and marks the start of the array $S$. The character right after % is $S[0]$, the next one is $S[1]$, and $S$ continues in the same order to the end of the line. The line therefore holds $2M + 1 + N$ characters.

$N$ and $M$ are not given separately. The position of % is $2M$, and the number of characters after it is $N$. E-Casino runs with $N = 2048$ and $M = 32$, which makes a line of 2113 characters, but inputs built from smaller settings also appear. In every case $1 \le M \le N \le 2048$.

The observed bits always come from some seed, so at least one valid $k$ exists.

Print the smallest value that $k$ can take in the secret seed.

The table below follows the computation of $r[0], r[1], \dots, r[5]$ for $N = 10$, $k = 4$, $M = 3$, and $m = \langle 1, 0, 1 \rangle$. The third row holds the array $S$. The values of $r[6]$ through $r[9]$ are left out to keep the table short.

          j       | 6 7 8 9 0 1 2 3 4 5
   (k + j) mod N  | 0 1 2 3 4 5 6 7 8 9
---------------------------------------
 S[(k + j) mod N] | 1 1 1 0 0 1 0 1 0 1
     m[j mod M]   |         1 0 1 1 0 1
---------------------------------------
         r[j]     |         1 1 1 0 0 0

The first six output bits are 1, 1, 1, 0, 0, 0. A gambler who sees only those six bits, and knows neither $k$ nor $m$, can still show that $k$ has to be 4: write down every combination of $k$ and $m$ and check which one produces those six bits. For $N = 2048$ and $M = 32$ that exhaustive search is hopeless.