math - XOR 和 mod 的交换性

Question

因此，在探索哈希函数时，我注意到以下等式：

((129*N)^prev)%256 = ((129*N)%256)^prev

对于 0 到 255 之间的任何数字N, prev。基本上你可以在不改变结果的情况下拖出 mod 操作，它只适用于数字 129。有人可以告诉我 129 有什么特别之处吗？

score 2 · Accepted Answer

在使用模运算时，会发生

(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存在，该属性都是有效的。256a129

129然而， as有一些非常特别的地方，1, 127, 129并且255是唯一的余数mod 256that r * r = 1 mod 256。还要注意255 = -1 (mod 256)和127 = -129 mod 256。

score 1 · Accepted Answer

如果将 256 的模数解释为 255 的按位与，或者换句话说，只保留最低有效的 8 位，这更容易看出。

显然，XOR 不会使来自较高位的信息传播到较低位（实际上在任何一个方向上都没有传播），因此无论“那里”发生什么，都不会对低位产生任何影响。它可能会对高位产生影响（XOR 可以设置，然后根据 AND 是先发生还是第二次发生，这些位分别保持设置或复位），但假设在这里不会发生。

代数上，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在这里调用了那个部分。

score 0 · Accepted Answer

0

独占或与加法模 2 完全相同。

于 2017-02-17T08:22:15.040 回答

3 回答 3