Java a une classe de nombres aléatoires appelée java.util.Random.
Il peut être utilisé comme suit:
python
int s = 32198541;
Random r = new Random(s); //La graine peut être spécifiée
int a = r.nextInt(24); //Quelque chose revient d'un entier de 0 à 23
int b = r.nextInt(24);
int c = r.nextInt(24);
Maintenant, comment «a» est-il obtenu à partir de «s» ici?
Il est clair que Random contient des variables internes, car Random # nextInt renvoie des valeurs différentes même si la même valeur est mangée. Ici, nous nommons la variable «seed» (qui est en fait le nom en interne).
Montre ce que fait le constructeur Random avec un pseudo-code presque Java.
long seed;
Random(long seed)
{
this.seed = (seed ^ 0x5DEECE66DL) & 0xFFFFFFFFFFFFL;
}
En fait, c'est le seul. Après que le bit XORing a une valeur étrange à la graine donnée, seuls les 48 bits inférieurs sont extraits. «0x5DEECE66DL» est «25214903917» en décimal et la factorisation première est «7 * 443 * 739 * 11003».
nextIntUne simplification audacieuse du comportement de Random # nextInt ressemble à ceci.
int nextInt(int bound)
{
seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
return ((int) (seed >> 17)) % bound;
}
Il est divisé en une partie de mise à jour de la graine et une partie de sortie de la valeur aléatoire obtenue à partir de la graine actuelle.
En résumé, la relation entre la graine donnée en premier et «nextInt» est à peu près la suivante.
long seed = 32198541; //Valeur de semences à donner
//Première perturbation des graines
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;
Voici le problème. Si nous connaissons le "seed3" dans le code ci-dessus, est-il possible de trouver facilement le "seed2"? Peut-être que si vous apprenez la théorie de la génération de nombres aléatoires, ce sera une tâche qui se terminera par un seul coup, mais ignorez ces choses et faites de votre mieux en vain.
Créez «x = f (z)» lorsque l'équation suivante existe.
z = (x * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
Ici, + 0xBL peut être géré en jouant un peu avec la valeur, alors supprimez-la. Ensuite, il peut être simplifié au problème suivant.
z = x * 0x5DEECE66DL % 0x1000000000000L
x = f(z)
Si vous connaissez ce «f», vous pouvez calculer la graine une étape avant.
0 <= x <= 0xFFFFFFFFFFFFL、
Lorsque z = x * 0x5DEECE66DL% 0x1000000000000L
«x» et «z» sont tous des plans uniques.
Tous les plans uniques sont comme la relation entre les nombres et l'ordre lorsque les cartes numérotées sont mélangées. Si vous êtes fort en mathématiques, c'est un problème qui se termine par un seul coup, mais je ne suis pas sûr, alors réfléchissez bien.
Tout d'abord, que faire si z = x * 7% 10? x * 7% 10 at 0> = x> = 9 devient 0 7 4 1 8 5 2 9 6 3, qui est un seul coup. Dans le cas de «z = x * 5% 10», il s'agit de «0 5 0 5 0 5 0 5 0 5» et pas tous d'un seul coup. Lorsque «z = x * y% 10», il y avait quatre «y» où «x» et «z» étaient tous des plans uniques, «1 3 7 9».
Ici, ce qui suit est supposé.
Lorsque 0 <= x <m, z = x * y% m,
Si l'engagement maximum de «y» et «m» est 1, alors «x» et «z» sont tous des plans uniques.
Puisqu'il est impossible pour un «x» d'avoir plusieurs «z», lorsque plusieurs «x» correspondent à un «z», il ne s'agit plus d'un seul tir. z = x * 10% 100 n'est pas un seul plan complet car il chevauche x = 0 lorsque x est un multiple de 10.
Cela peut être considéré comme une boucle tous les 10 lorsque «x» est incrémenté de 0 par 1. Autrement dit, lorsque «z = x * 3% 100», une boucle se produit lorsque «x» dépasse la plage et devient 100, mais lorsque «z = x * 10% 100», 10 boucles peuvent être créées. Ce n'est pas un seul coup parce qu'il finira.
Quand «x * y» rend-il la boucle plus courte que «m», en d'autres termes, revient à «x * y% m == 0»? Le fait que «x * y» soit divisible par «m» signifie que «x * y» est un multiple de «m». Et si tous les facteurs de «m» sont également inclus dans «x * y», ce sera un multiple de «m». Par exemple, «12 (= 2 * 2 * 3) * 15 (= 3 * 5)» est un multiple de «60 (= 2 * 2 * 3 * 5)». Ensuite, lorsque «y» ne contient aucune fraction de «m», «x» boucle tous les «m». Si "y" contient une fraction de "m", "x" sera suffisant avec la fraction de "y" même si la fraction ne suffit pas.
En résumé, si l'engagement maximum de «y» et «m» est 1, alors «x» et «z» sont tous des plans uniques. Supposons que l'hypothèse 2 est correcte pour le moment.
Ensuite, puisque 0x5DEECE66DL = 25214903917 = 7 * 443 * 739 * 11003, le numéro d'engagement maximum avec 0x1000000000000L est 1, donc l'hypothèse 1 est également correcte.
En regardant la série «0 7 4 1 8 5 2 9 6 3» de «z = x * 7% 10», la place des unités de «0 21 12 3 24 15 6 27 18 9» multipliée par 3 est l'ordre. Remarquerez que. Autrement dit, «x = z * 3% 10».
Par conséquent, ce qui suit est supposé.
Lorsque 0 <= x <m, z = x * y% m,
Il existe un "w" qui satisfait "x = z * w% m".
En raison de la symétrie de la définition, pour le seul compagnon de «y», le seul compagnon de «w» est «y».
La substitution donne «z = (z * w% m) * y% m». Puisque la partie «(z * w% m) * y» est la même même si elle augmente de «m», il n'y a aucun point dans «% m» à «z * w% m». Vous pouvez donc écrire z = z * w * y% m. Pour «z», «* w * y% m» est toujours «z», ce qui signifie probablement «w * y% m == 1».
Pour le moment, j'ai essayé d'énumérer y: w quand m = 100, 64 dans le 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:wQuandw:yOn peut le confirmer. Aussi,y * w % mÉtait calculé pour être tout 1. pour cette raisonm = 100QuandyQuandwの1の位をかけるQuand必ず1の位が1になる。そのため1の位は必ず1:1|3:7|7:3|9:9Quand対応している。九九表の中で1の位が1である場所はそこしかないのだ。
Et il peut être utilisé comme fonction pour trouver correctement «x» comme suit.
52 = 76 * 27 % 100
76 = 52 * 63 % 100
27 * 63 = 1701
Le même calcul peut être fait avec un plus grand nombre.
3596 = 7852 * 273 % 10000
7852 = 3596 * 6337 % 10000
273 * 6337 = 1730001
L'hypothèse 3 est correcte pour le moment. La recherche d'un «w» tel que «y * w% m == 1» est probablement une condition suffisante pour calculer «x = f (z)».
Au fait, vous pouvez rechercher le compagnon de 0x5DEECE66DL en poussant GPGPU, mais j'ai confirmé la propriété intéressante que" la 1ère place est fixée lorsque m = 100". Cela devrait également être vrai pour les nombres hexadécimaux.
En réalité,m = 64Au moment de la 1ère place1:1|3:B|5:D|7:7|9:9|B:3|D:5|F:FIl y a une correspondance. Seulement avec cette combinaison0001Il semble que le nombre binaire ne puisse pas être généré dans les 4 bits inférieurs. Lorsqu'il est effectivement multiplié, le reste divisé par 16 devient 1 comme indiqué ci-dessous.
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
Ce que l'on peut en dire, c'est que la 1ère place de «0x5DEECE66DL» est «0x5». Cela nécessite à lui seul 1/16 du montant du calcul. Cependant, lorsque m = 64, il n'y a aucune raison pour que cela puisse être fait en notation hexadécimale mais pas en notation 256 décimale. Peut-être est-il correct de séparer tous les deux chiffres en hexadécimal.
Alors, essayez de trouver le compagnon w of z = x * 0x6D% 0x100. Le compagnon est «0x65» et «0x6D * 0x65 = 0x2B01». Avec cela, on peut prédire que les deux derniers chiffres du compagnon de «0x5DEECE66DL» sont «0x65».
Le compagnon de z = x * 0xE66D% 0x10000 est 0x1365, et lorsqu'il est multiplié, il devient 0x11750001. Ce calcul peut être fait en générant les candidats de l'autre partie dans l'ordre et en vérifiant s'il devient 1 par * 0xE66D% 0x10000, mais puisque nous savons que les deux derniers chiffres de l'autre partie sont 0x65, Vous n'avez qu'à boucler les deux chiffres restants.
Le compagnon de z = x * 0x5DEECE66DL% 0x1000000000000L est 0xDFE05BCB1365L et 0x5DEECE66DL * 0xDFE05BCB1365L = 0x86E9000000000001. Nous pouvons maintenant trouver la fonction inverse de la partie multiplication.
z = x * 0x5DEECE66DL & 0xFFFFFFFFFFFFL
x = z * 0xDFE05BCB1365L & 0xFFFFFFFFFFFFL
Après cela, ajoutez une petite partie + 0xBL et vous avez terminé.
z = (x * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
x = (z - 0xBL) * 0xDFE05BCB1365L & 0xFFFFFFFFFFFFL
La graine de Random peut être recalculée comme suit.
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));
résultat
86e8d09b41f2
32522523
Recommended Posts