Так, исследуя хеш-функцию я заметил следующее уравнение:Перестановочности XOR и моды
((129*N)^prev)%256 = ((129*N)%256)^prev
Для любого числа N, prev в диапазоне от 0 до 255. В принципе вы можете перетащить моды операции без изменения результата, и он работает только на номер 129. Может кто-нибудь может сказать мне, что так особенного в 129?
Это проще понять, если вы интерпретируете это по модулю 256 как побитовое И на 255, или, другими словами, сохраняете только наименее значимые 8 бит.
Понятно, что XOR не делает информацию от более высоких бит, перемещаемых к нижним битам (на самом деле нет движения в любом направлении), поэтому все, что происходит «там», не может иметь никакого значения для низких бит. Это могло бы иметь значение для высоких бит (которые XOR мог установить, а затем в зависимости от того, происходит ли первое или второе событие AND, эти биты соответственно сохраняются установленными или сброшенными), но по предположению, что этого не может быть здесь.
алгебраически, и распространяет через XOR, так
(a^b) & c =
& distributes over^
(a & c)^(b & c)
И мы имеем, что b & c = b потому c 255 и b находится в диапазоне от 0 до 255, так
(a & c)^(b & c) =
by assumptions
(a & c)^b
Это не связана с умножение, это могло быть буквально что угодно, я только что назвал эту часть a здесь.
При работе с модульной арифметикой случается, что
(a*b) mod m = ((a mod m) * (b mod m)) mod m
Если применить это свойство b = a
a^2 mod m = (a mod m)^2 mod m
и повторять одни и те же n раз
a^n mod m = (a mod m)^n mod m
И так как это действителен для любого значения a, мы также получаем
(a*b)^n mod m = (a*b mod m)^n mod m
Таким образом, свойство действует независимо от m быть 256 или нет, и a быть 129 или нет.
Существует, однако, нечто совершенно особенное 129, как 1, 127, 129 и 255 являются единственными остатками mod 256 таким образом, что r * r = 1 mod 256. Отметим также, что 255 = -1 (mod 256) и 127 = -129 mod 256.
исключающее или работает точно так же, как сложение по модулю 2.