Java has a random number class called java.util.Random.
It can be used as follows:
python
int s = 32198541;
Random r = new Random(s); //Seed can be specified
int a = r.nextInt(24); //Something returns for an integer from 0 to 23
int b = r.nextInt(24);
int c = r.nextInt(24);
Now, how is ʻa obtained from shere? It is clear that Random contains internal variables, becauseRandom # nextIntreturns different values even if the same value is eaten. Here we name the variableseed` (which is actually the name internally).
Shows what the Random constructor is doing with almost Java pseudocode.
long seed;
Random(long seed)
{
this.seed = (seed ^ 0x5DEECE66DL) & 0xFFFFFFFFFFFFL;
}
In fact, this is the only one.
After bit-XORing a strange value to the given seed, only the lower 48 bits are extracted.
0x5DEECE66DL is 25214903917 in decimal and the prime factorization is 7 * 443 * 739 * 11003.
nextIntA bold simplification of the behavior of Random # nextInt looks like this.
int nextInt(int bound)
{
seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
return ((int) (seed >> 17)) % bound;
}
It is divided into an update part of the seed and an output part of the random value obtained from the current seed.
Summarizing these, the relationship between the seed given first and nextInt is roughly as follows.
long seed = 32198541; //Seed value to give
//First seed disturbance
seed = (seed ^ 0x5DEECE66DL) & 0xFFFFFFFFFFFFL;
// nextInt
long seed2 = seed;
seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
long seed3 = seed;
int a = ((int) (seed >> 17)) % 24;
// nextInt
seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
int b = ((int) (seed >> 17)) % 24;
// nextInt
seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
int c = ((int) (seed >> 17)) % 24;
Here is the problem. If we know the seed3 in the code above, is it possible to easily find the seed2?
Perhaps if you learn the theory of random number generation, it will be a task that will end with a single blow, but ignore such things and do your best in vain.
Create x = f (z) when the following equation exists.
z = (x * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
Here, + 0xBL can be managed by playing with the value a little, so remove it. Then it can be simplified to the next problem.
z = x * 0x5DEECE66DL % 0x1000000000000L
x = f(z)
If you know this f, you can calculate the seed one step before.
0 <= x <= 0xFFFFFFFFFFFFL、
When z = x * 0x5DEECE66DL% 0x1000000000000L,
x and z are bijective.
Bijection is like the relationship between numbers and order when shuffling numbered cards. If you are strong in mathematics, this is a problem that ends with a single blow, but I'm not sure, so think appropriately.
First, what if z = x * 7% 10? x * 7% 10 at 0> = x> = 9 becomes 0 7 4 1 8 5 2 9 6 3 and is bijective. In the case of z = x * 5% 10, 0 5 0 5 0 5 0 5 0 5 is not bijective. When z = x * y% 10, there were four ys where x and z were bijective, 1 3 7 9.
Here, the following is assumed.
When 0 <= x <m, z = x * y% m,
If the greatest common divisor of y and m is 1, then x and z are bijective.
Since it is impossible for one x to have multiple zs, when multiple xs correspond to one z, it is not bijective. z = x * 10% 100 is not bijective because it overlaps with x = 0 when x is a multiple of 10.
This can be thought of as looping every 10 when x is incremented from 0 by 1. That is, when z = x * 3% 100, a loop occurs when x exceeds the range and reaches 100, but when z = x * 10% 100, 10 loops can be created. It is not a bijection because it ends up.
When does x * y make the loop shorter than m, in other words, return to x * y% m == 0? The fact that x * y is divisible by m means that x * y is a multiple of m. And if all the factors of m are also included in x * y, it will be a multiple of m. For example, 12 (= 2 * 2 * 3) * 15 (= 3 * 5) is a multiple of 60 (= 2 * 2 * 3 * 5).
Then, when y does not contain any divisor of m, x loops every m. If y contains one divisor of m, x will be enough together with the divisor of y even if the divisor is not enough.
In summary, if the greatest common divisor of y and m is 1, then x and z are bijective. For the time being, let's assume that Assumption 2 is correct.
Then, since 0x5DEECE66DL = 25214903917 = 7 * 443 * 739 * 11003, the greatest common divisor with 0x1000000000000L is 1, so assumption 1 is also correct.
Looking at the series 0 7 4 1 8 5 2 9 6 3 of z = x * 7% 10, the ones place of 0 21 12 3 24 15 6 27 18 9 multiplied by 3 is the order. Notice that. That is, x = z * 3% 10.
Therefore, the following is assumed.
When 0 <= x <m, z = x * y% m,
There exists a w that satisfies x = z * w% m.
Due to the symmetry of the definition, for the only companion to y, the only companion to w is y.
Substitution gives z = (z * w% m) * y% m. Since the (z * w% m) * y part is the same even if it increases by m, there is no point in % m at z * w% m. So you can write z = z * w * y% m. For z, * w * y% m is still z, which probably means w * y% m == 1.
For the time being, I tried to enumerate y: w when m = 100, 64 in the script.
m=100
1:1|3:67|7:43|9:89|11:91|13:77|17:53|19:79|21:81|23:87|27:63|29:69
31:71|33:97|37:73|39:59|41:61|43:7|47:83|49:49|51:51|53:17|57:93|59:39
61:41|63:27|67:3|69:29|71:31|73:37|77:13|79:19|81:21|83:47|87:23|89:9
91:11|93:57|97:33|99:99
m=64
1:1|3:43|5:13|7:55|9:57|11:35|13:5|15:47|17:49|19:27
21:61|23:39|25:41|27:19|29:53|31:31|33:33|35:11|37:45|39:23
41:25|43:3|45:37|47:15|49:17|51:59|53:29|55:7|57:9|59:51
61:21|63:63
1:1|3:2B|5:D|7:37|9:39|B:23|D:5|F:2F
11:31|13:1B|15:3D|17:27|19:29|1B:13|1D:35|1F:1F
21:21|23:B|25:2D|27:17|29:19|2B:3|2D:25|2F:F
31:11|33:3B|35:1D|37:7|39:9|3B:33|3D:15|3F:3F
y:wWhenw:yIt can be confirmed that. Also,y * w % mWas calculated to be all 1. for that reasonm = 100WhenyWhenwの1の位をかけるWhen必ず1の位が1になる。そのため1の位は必ず1:1|3:7|7:3|9:9When対応している。九九表の中で1の位が1である場所はそこしかないのだ。
And it can be used as a function to find x properly as follows.
52 = 76 * 27 % 100
76 = 52 * 63 % 100
27 * 63 = 1701
The same calculation can be done with a larger number.
3596 = 7852 * 273 % 10000
7852 = 3596 * 6337 % 10000
273 * 6337 = 1730001
Assumption 3 is correct for the time being. Probably looking for a w such as y * w% m == 1 is a sufficient condition to calculate x = f (z).
By the way, you can search for the companion of 0x5DEECE66DL by pushing GPGPU, but I confirmed the interesting property that" the 1st place is fixed when m = 100". This should also be true for hexadecimal numbers.
In fact,m = 64At the time of 1st place1:1|3:B|5:D|7:7|9:9|B:3|D:5|F:FThere is a correspondence called. Only with this combination0001It seems that the binary number cannot be generated in the lower 4 bits. When actually multiplied, the remainder divided by 16 becomes 1 as shown below.
0x1 * 0x1 = 1 = 0 * 16 + 1
0x3 * 0xB = 33 = 2 * 16 + 1
0x7 * 0x7 = 49 = 3 * 16 + 1
0x5 * 0xD = 65 = 4 * 16 + 1
0x9 * 0x9 = 81 = 5 * 16 + 1
0xF * 0xF = 225 = 14 * 16 + 1
What can be said from this is that the 1st place of the 0x5DEECE66DL is 0x5. This alone requires 1/16 the amount of calculation. However, when m = 64, there is no reason why it can be done in hexadecimal notation but not in 256 decimal notation. Perhaps it's okay to separate every two digits in hexadecimal.
So, try to find the companion w of z = x * 0x6D% 0x100. The companion is 0x65 and 0x6D * 0x65 = 0x2B01. With this, it can be predicted that the last two digits of the companion of 0x5DEECE66DL are 0x65.
The companion of z = x * 0xE66D% 0x10000 is 0x1365, and when multiplied, it becomes 0x11750001. This calculation can be done by generating the candidates of the companion in order and checking if it becomes 1 by * 0xE66D% 0x10000, but since we know that the last two digits of the companion are 0x65, You only have to loop the remaining two digits.
The companion to z = x * 0x5DEECE66DL% 0x1000000000000L is 0xDFE05BCB1365L and 0x5DEECE66DL * 0xDFE05BCB1365L = 0x86E9000000000001. Now we can find the inverse function of the multiplication part.
z = x * 0x5DEECE66DL & 0xFFFFFFFFFFFFL
x = z * 0xDFE05BCB1365L & 0xFFFFFFFFFFFFL
After that, add a little + 0xBL part and you're done.
z = (x * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
x = (z - 0xBL) * 0xDFE05BCB1365L & 0xFFFFFFFFFFFFL
The seed of Random can be calculated back as follows.
long seed = 0x32522523;
seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
System.out.println(String.format("%x", seed));
seed = (seed - 0xBL) * 0xDFE05BCB1365L & 0xFFFFFFFFFFFFL;
System.out.println(String.format("%x", seed));
result
86e8d09b41f2
32522523
Recommended Posts