Java hat eine Zufallszahlenklasse namens "java.util.Random". Es kann wie folgt verwendet werden:
python
int s = 32198541;
Random r = new Random(s); //Samen kann angegeben werden
int a = r.nextInt(24); //Von einer Ganzzahl von 0 bis 23 kehrt etwas zurück
int b = r.nextInt(24);
int c = r.nextInt(24);
Wie kann man hier ein "a" von "s" erhalten?
Es ist klar, dass Random interne Variablen enthält, da Random # nextInt unterschiedliche Werte zurückgibt, selbst wenn derselbe Wert gegessen wird. Hier nennen wir die Variable "seed" (was eigentlich der interne Name ist).
Zeigt, was der Zufallskonstruktor mit fast Java-Pseudocode macht.
long seed;
Random(long seed)
{
this.seed = (seed ^ 0x5DEECE66DL) & 0xFFFFFFFFFFFFL;
}
In der Tat ist dies der einzige.
Nachdem Bit X einen seltsamen Wert für den angegebenen Startwert eingegeben hat, werden nur die unteren 48 Bits extrahiert.
0x5DEECE66DL ist 25214903917 in Dezimalzahl und die Primfaktorisierung ist 7 * 443 * 739 * 11003.
nextIntEine kühne Vereinfachung des Verhaltens von Random # nextInt sieht so aus.
int nextInt(int bound)
{
seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
return ((int) (seed >> 17)) % bound;
}
Es ist in einen Aktualisierungsteil des Startwerts und einen Ausgabeteil des Zufallswerts unterteilt, der aus dem aktuellen Startwert erhalten wird.
Zusammenfassend ist die Beziehung zwischen dem zuerst angegebenen Startwert und "nextInt" ungefähr wie folgt.
long seed = 32198541; //Samenwert zu geben
//Erste Samenstörung
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;
Hier ist das Problem. Wenn wir den "seed3" im obigen Code kennen, ist es dann möglich, den "seed2" leicht zu finden? Wenn Sie die Theorie der Zufallszahlengenerierung lernen, wird es vielleicht eine Aufgabe sein, die mit einem einzigen Schlag endet, aber ignorieren Sie solche Dinge und geben Sie vergeblich Ihr Bestes.
Erstellen Sie "x = f (z)", wenn die folgende Gleichung existiert.
z = (x * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
Hier kann + 0xBL verwaltet werden, indem ein wenig mit dem Wert gespielt wird. Entfernen Sie ihn also. Dann kann es zum nächsten Problem vereinfacht werden.
z = x * 0x5DEECE66DL % 0x1000000000000L
x = f(z)
Wenn Sie dieses f kennen, können Sie den Startwert einen Schritt vorher berechnen.
0 <= x <= 0xFFFFFFFFFFFFL、
Wenn z = x * 0x5DEECE66DL% 0x1000000000000L
x und z sind alles Einzelaufnahmen.
Alle Einzelschüsse sind wie die Beziehung zwischen Zahlen und Reihenfolge, wenn nummerierte Karten gemischt werden. Wenn Sie stark in Mathematik sind, ist dies ein Problem, das mit einem einzigen Schlag endet, aber ich bin mir nicht sicher, also denken Sie angemessen.
Was ist, wenn "z = x * 7% 10"? "x * 7% 10" bei "0> = x> = 9" wird zu "0 7 4 1 8 5 2 9 6 3", was alles Einzelschuss ist. Im Fall von "z = x * 5% 10" ist es "0 5 0 5 0 5 0 5 0 5" und nicht alle Einzelschüsse. Wenn "z = x * y% 10", gab es vier "y", wobei "x" und "z" alle Einzelaufnahmen waren, "1 3 7 9".
Hier wird folgendes angenommen.
Wenn "0 <= x <m", "z = x * y% m", Wenn die maximale Verpflichtung von "y" und "m" 1 ist, sind "x" und "z" alles Einzelschüsse.
Da es unmöglich ist, dass ein "x" mehrere "z" hat, ist es kein einziger Schuss mehr, wenn mehrere "x" einem "z" entsprechen. Der Grund, warum "z = x * 10% 100" kein vollständiger Einzelschuss ist, ist, dass wenn "x" ein Vielfaches von 10 ist, es sich mit "z = 0" und "x = 0" überlappt.
Dies kann als Schleife alle 10 angesehen werden, wenn x von 0 um 1 erhöht wird. Das heißt, wenn "z = x * 3% 100" ist, tritt eine Schleife auf, wenn "x" den Bereich überschreitet und 100 wird, aber wenn "z = x * 10% 100" ist, können 10 Schleifen erzeugt werden. Es ist kein einziger Schuss, weil er enden wird.
Wann macht "x * y" die Schleife kürzer als "m", dh kehrt zu "x * y% m == 0" zurück? Die Tatsache, dass "x * y" durch "m" teilbar ist, bedeutet, dass "x * y" ein Vielfaches von "m" ist. Und wenn alle Faktoren von "m" auch in "x * y" enthalten sind, ist es ein Vielfaches von "m". Zum Beispiel ist "12 (= 2 * 2 * 3) * 15 (= 3 * 5)" ein Vielfaches von "60 (= 2 * 2 * 3 * 5)". Wenn dann "y" keinen Bruchteil von "m" enthält, schleift "x" jedes "m". Wenn "y" einen Bruchteil von "m" enthält, reicht "x" zusammen mit dem Bruchteil von "y" aus, auch wenn der Bruch nicht ausreicht.
Zusammenfassend ist, wenn die maximale Verpflichtung von "y" und "m" 1 ist, "x" und "z" alles Einzelschüsse. Nehmen wir an, dass Annahme 2 vorerst richtig ist. Da dann "0x5DEECE66DL = 25214903917 = 7 * 443 * 739 * 11003" ist, ist die maximale Verpflichtungsnummer mit "0x1000000000000L" 1, sodass auch Annahme 1 korrekt ist.
Betrachtet man die Reihe "0 7 4 1 8 5 2 9 6 3" von "z = x * 7% 10", so ist die Stelle von "0 21 12 3 24 15 6 27 18 9" multipliziert mit 3 die Reihenfolge Beachte das. Das heißt, "x = z * 3% 10".
Daher wird Folgendes angenommen.
Wenn "0 <= x <m", "z = x * y% m", Es gibt ein "w", das "x = z * w% m" erfüllt.
Aufgrund der Symmetrie der Definition ist für den einzigen Begleiter zu "y" der einzige Begleiter zu "w" "y".
Die Substitution führt zu "z = (z * w% m) * y% m". Da der Teil "(z * w% m) * y" der gleiche ist, selbst wenn er um "m" zunimmt, hat "% m" bei "z * w% m" keinen Sinn. Sie können also "z = z * w * y% m" schreiben. Für "z" ist "* w * y% m" immer noch "z", was wahrscheinlich "w * y% m == 1" bedeutet.
Vorerst habe ich versucht, "y: w" aufzulisten, wenn "m = 100, 64" im Skript ist.
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:wWannw:yEs kann bestätigt werden, dass. Ebenfalls,y * w % mWurde berechnet, um alle 1 zu sein. aus diesem Grundm = 100WannyWannwの1の位をかけるWann必ず1の位が1になる。そのため1の位は必ず1:1|3:7|7:3|9:9Wann対応している。九九表の中で1の位が1である場所はそこしかないのだ。
Und es kann als Funktion verwendet werden, um "x" wie folgt richtig zu finden.
52 = 76 * 27 % 100
76 = 52 * 63 % 100
27 * 63 = 1701
Die gleiche Berechnung kann mit einer größeren Anzahl durchgeführt werden.
3596 = 7852 * 273 % 10000
7852 = 3596 * 6337 % 10000
273 * 6337 = 1730001
Annahme 3 ist vorerst richtig. Wahrscheinlich ist die Suche nach einem "w" wie "y * w% m == 1" eine ausreichende Bedingung, um "x = f (z)" zu berechnen.
Übrigens können Sie nach dem Begleiter von "0x5DEECE66DL" suchen, indem Sie GPGPU drücken, aber ich habe die interessante Eigenschaft bestätigt, dass "der 1. Platz festgelegt ist, wenn" m = 100 "". Dies sollte auch für Hexadezimalzahlen gelten.
Eigentlich,m = 64Zum Zeitpunkt des 1. Platzes1:1|3:B|5:D|7:7|9:9|B:3|D:5|F:FEs gibt eine Korrespondenz. Nur mit dieser Kombination0001Es scheint, dass die Binärzahl nicht in den unteren 4 Bits generiert werden kann. Bei tatsächlicher Multiplikation wird der durch 16 geteilte Rest wie unten gezeigt zu 1.
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
Daraus lässt sich schließen, dass der 1. Platz der 0x5DEECE66DL`` 0x5 ist. Dies allein erfordert 1/16 des Berechnungsbetrags. Wenn jedoch "m = 64" ist, gibt es keinen Grund, warum dies in hexadezimaler Notation, jedoch nicht in 256-dezimaler Notation erfolgen kann. Vielleicht ist es in Ordnung, alle zwei Ziffern hexadezimal zu trennen.
Versuchen Sie also, den Begleiter w von z = x * 0x6D% 0x100 zu finden. Der Begleiter ist "0x65" und "0x6D * 0x65 = 0x2B01". Damit können wir vorhersagen, dass die letzten beiden Ziffern des Begleiters von "0x5DEECE66DL" "0x65" sind.
Der Begleiter von "z = x * 0xE66D% 0x10000" ist "0x1365", und wenn er multipliziert wird, wird er zu "0x11750001". Diese Berechnung kann durchgeführt werden, indem die Kandidaten der anderen Partei der Reihe nach generiert und überprüft werden, ob sie durch "* 0xE66D% 0x10000" zu 1 wird. Da wir jedoch wissen, dass die letzten beiden Ziffern der anderen Partei "0x65" sind, Sie müssen nur die verbleibenden zwei Ziffern schleifen.
Der Begleiter zu "z = x * 0x5DEECE66DL% 0x1000000000000L" ist "0xDFE05BCB1365L" und "0x5DEECE66DL * 0xDFE05BCB1365L = 0x86E9000000000001". Nun können wir die Umkehrfunktion des Multiplikationsteils finden.
z = x * 0x5DEECE66DL & 0xFFFFFFFFFFFFL
x = z * 0xDFE05BCB1365L & 0xFFFFFFFFFFFFL
Danach fügen Sie einen kleinen + 0xBL Teil hinzu und fertig.
z = (x * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
x = (z - 0xBL) * 0xDFE05BCB1365L & 0xFFFFFFFFFFFFL
Der Startwert von Random kann wie folgt zurückgerechnet werden.
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));
Ergebnis
86e8d09b41f2
32522523
Recommended Posts