CODEWITHSUNDEEP
mathbit-manipulationxormodulo
Yifan Zhu
Yifan Zhu

Reputation: 45

Commutativity of XOR and mod

So when exploring hash functions I noticed the following equation:

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

For any number N, prev between 0 and 255. Basically you can drag the mod operation out without changing the result, and it only works for number 129. Can somebody maybe tell me what is so special about 129?

Upvotes: 4

Views: 6225

Answers (3)

daniel
daniel

Reputation: 471

exclusive or works exactly like addition modulo 2.

https://en.wikipedia.org/wiki/Exclusive_or

Upvotes: 0

user555045
user555045

Reputation: 64913

This is easier to see if you interpret that modulo by 256 as bitwise AND by 255, or in other words, keeping only the least significant 8 bits.

Clearly the XOR does not make information from the higher bits travel to the lower bits (actually there's no traveling in either direction), so whatever happens "up there" cannot make any difference for the low bits. It could have made a difference for the high bits (which the XOR could set, and then depending on whether the AND happens first or second, those bits are respectively kept set or reset), but by assumption that cannot happen here.

Algebraically, AND distributes over XOR, so

(a ^ b) & c =
& distributes over ^
(a & c) ^ (b & c)

And we have that b & c = b because c is 255 and b is between 0 and 255, so

(a & c) ^ (b & c) =
by assumptions
(a & c) ^ b

This is not related to the multiplication, it could have been literally anything, I've just called that part a here.

Upvotes: 3

Leandro Caniglia
Leandro Caniglia

Reputation: 14868

When working with modular arithmetic it happens that

(a*b) mod m = ((a mod m) * (b mod m)) mod m

If you apply this property to b = a

a^2 mod m = (a mod m)^2 mod m

and repeating the same n times

a^n mod m = (a mod m)^n mod m

And since this is valid for any value of a, we also get

(a*b)^n mod m = (a*b mod m)^n mod m

So, the property is valid regardless of m being 256 or not and a being 129 or not.

There is however something quite special about 129 as 1, 127, 129 and 255 are the only remainders mod 256 such that r * r = 1 mod 256. Note also that 255 = -1 (mod 256) and 127 = -129 mod 256.

Upvotes: 1

Related Questions