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, because
Random # nextIntreturns different values even if the same value is eaten. Here we name the variable
seed` (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
.
nextInt
A 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 y
s 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 z
s, when multiple x
s 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:w
Whenw:y
It can be confirmed that. Also,y * w % m
Was calculated to be all 1. for that reasonm = 100
Wheny
Whenw
の1の位をかけるWhen必ず1の位が1になる。そのため1の位は必ず1:1|3:7|7:3|9:9
When対応している。九九表の中で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 = 64
At the time of 1st place1:1|3:B|5:D|7:7|9:9|B:3|D:5|F:F
There is a correspondence called. Only with this combination0001
It 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