Problem Statement |
| | In this problem your task is to break a pseudorandom number generator given its last K outputs. Each `random' number will be generated as a function of the previous M `random' numbers, for some M. After the function is evaluated, the result is taken modulo a prime P, and that is the output. For instance, a simple generator function would be Sn = Sn-1+Sn-2 (mod P). A more complicated one is Sn = Sn-11*Sn-2 + Sn-1 + 1 (mod P). In general we will consider polynomials functions of the last M numbers. Your task is to write a method crack that takes a int[] S, a int, M, an int P, and returns your best guess for the next M numbers output by the generator.
The prime, P will be between 101 and 40000, inclusive. M will be chosen as floor(rand()*rand()*996)+5, where rand() is a uniform random number in [0,1].
The polynomial will be generated by first picking D, the maximum degree as 1, 2, or 3. The number of terms will then be chosen in [2,min(200,1+M+(D>1?M(M+1)/2)+(D>2?M(M+1)(M+2)/6)], and each term will be generated with a degree in [0,D]. After the degree d is chosen, d (not necessarily distinct) previous random numbers (offsets) are selected as the components of the term. If this generates a term which has already been generated, the process is repeated (so, degree 0 will only occur once, for instance). After the variables are chosen, the coefficient is chosen in [0,P-1]. You will be given the K sequential random numbers for K in [M,min(1000000,3*MD)]. The random number generator will be initialized with M random values, and then run for K+100*M iterations, of which you will be given the final K.
All random choices are uniform and independent.
Your score will be the number of the M entries that are correct. Your overall score will simply be the sum of your individual scores.
You can download the source code and class files to generate a sequence of random numbers. To run, simply enter 'java LaggedGenerator <seed>'. The output will be the M initial values, followed by an asterisk, followed by 100M random values, followed by an asterisk, followed by K random values, followed by an asterisk, and finally the M values to predict. The seeds for the examples are 1-9 and 18, in order. |
| |
Definition |
| | | Class: | LaggedGenerator | | Method: | crack | | Parameters: | int[], int, int | | Returns: | int[] | | Method signature: | int[] crack(int[] S, int P, int M) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The time limit is 30 seconds. |
| - | The memory limit is 1024M. |
| - | In the examples, N is the number of terms in the polynomial. |
| - | There are 100 non-example test cases. |
| |
Examples |
| 0) | |
| | | Returns: "" | P = 101
N = 4
D = 2
M = 5
K = 50
|
|
|
| 1) | |
| | | Returns: "" | P = 36299
N = 7
D = 1
M = 16
K = 44
|
|
|
| 2) | |
| | | Returns: "" | P = 23789
N = 177
D = 3
M = 102
K = 668069
|
|
|
| 3) | |
| | | Returns: "" | P = 13687
N = 62
D = 2
M = 155
K = 4147
|
|
|
| 4) | |
| | | Returns: "" | P = 28403
N = 26
D = 1
M = 25
K = 40
|
|
|
| 5) | |
| | | Returns: "" | P = 17257
N = 19
D = 3
M = 611
K = 682883
|
|
|
| 6) | |
| | | Returns: "" | P = 21481
N = 51
D = 1
M = 115
K = 193
|
|
|
| 7) | |
| | | Returns: "" | P = 24281
N = 180
D = 2
M = 211
K = 125395
|
|
|
| 8) | |
| | | Returns: "" | P = 27847
N = 127
D = 1
M = 565
K = 928
|
|
|
| 9) | |
| | | Returns: "" | P = 39317
N = 169
D = 2
M = 26
K = 1485
|
|
|