Коммутативность XOR и mod
Итак, исследуя хэш-функции, я заметил следующее уравнение:
((129*N)^prev)%256 = ((129*N)%256)^prev
Для любого числа N, prev между 0 и 255. В принципе, вы можете перетащить операцию mod, не изменяя результат, и это работает только для числа 129. Может быть, кто-нибудь скажет мне, что такого особенного в 129?
3 ответов:
Это легче увидеть, если вы интерпретируете это по модулю 256 как побитовое и 255, или другими словами, сохраняя только наименее значимые 8 бит.
Очевидно, что XOR не заставляет информацию от старших битов перемещаться к младшим битам (на самом деле нет никакого перемещения ни в том, ни в другом направлении), поэтому все, что происходит "там", не может иметь никакого значения для младших битов. Это могло бы иметь значение для старших битов (которые XOR может установить, а затем в зависимости от того, является ли и происходит первый или второй, эти биты соответственно сохраняются установленными или сброшенными), но по предположению, что здесь не может произойти.Алгебраически и распределяет по 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) ^ baздесь.
При работе с модульной арифметикой случается, что
(a*b) mod m = ((a mod m) * (b mod m)) mod mЕсли применить это свойство к
b = aa^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 mm256или нет иa129или нет.Однако есть нечто совершенно особенное в
129, поскольку1, 127, 129и255являются единственными остаткамиmod 256, такими чтоr * r = 1 mod 256. Отметим также, что255 = -1 (mod 256)и127 = -129 mod 256.
Comments