math - XOR 和 mod 的交换性

Question

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

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

对于 0 到 255 之间的任何数字 N, prev。基本上你可以将 mod 操作拖出而不改变结果，它只适用于数字 129。有人可以告诉我这是怎么回事吗特价约129？

Answer 1

在使用模块化算法时，会发生这种情况

(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。