wenn Hash-Funktionen zu erforschen, bemerkte ich die folgende Gleichung:Kommutativität von XOR und mod
((129*N)^prev)%256 = ((129*N)%256)^prev
für eine beliebige Anzahl N, prev zwischen 0 und 255. Grundsätzlich können Sie die Mod Operation in die Länge ziehen, ohne das Ergebnis zu ändern, und es funktioniert nur für Nummer 129. Kann mir vielleicht jemand sagen, was an 129 so besonders ist?
Dies ist einfacher zu sehen, wenn Sie diesen Modulo mit 256 als bitweises UND mit 255 interpretieren, oder mit anderen Worten, nur die niedrigstwertigen 8 Bits behalten.
Offensichtlich bringt das XOR keine Information von den höheren Bits zu den unteren Bits (tatsächlich gibt es keine Bewegung in beide Richtungen), was auch immer "da oben" passiert, kann für die niedrigen Bits keinen Unterschied machen. Es hätte einen Unterschied machen können für die hohen Bits (die das XOR setzen könnte, und dann abhängig davon, ob das UND zuerst oder zweit passiert, diese Bits werden jeweils gesetzt oder zurückgesetzt), aber durch Annahme, dass dies hier nicht passieren kann.
algebraisch und verteilt über XOR, so
(a^b) & c =
& distributes over^
(a & c)^(b & c)
Und wir haben das b & c = b weil c 255 und b liegt zwischen 0 und 255, so
(a & c)^(b & c) =
by assumptions
(a & c)^b
dies nicht die in Beziehung steht Multiplikation, es könnte buchstäblich alles sein, ich habe gerade diesen Teil a hier genannt.
Wenn mit modularer Arithmetik arbeiten passiert es, dass
(a*b) mod m = ((a mod m) * (b mod m)) mod m
Wenn Sie diese Eigenschaft auf b = a
a^2 mod m = (a mod m)^2 mod m
gelten und Wiederholen der gleichen n mal
a^n mod m = (a mod m)^n mod m
Und da dies gültig für jeden Wert von a, wir bekommen auch
(a*b)^n mod m = (a*b mod m)^n mod m
also die Eigenschaft gültig ist, unabhängig von m256 ist oder nicht, und a129 oder nicht.
Es ist aber etwas ganz Besonderes 129 als 1, 127, 129 und 255 sind die einzigen Reste mod 256 so dass r * r = 1 mod 256. Beachten Sie auch, dass 255 = -1 (mod 256) und 127 = -129 mod 256.
exklusiv oder funktioniert genau wie Addition modulo 2.