[Math] Cyclic redundancy check: yet another interesting feature
"CRC is a linear function with a property that crc(x ⊕ y) = crc(x) ⊕ crc(y)"
( src )

Why is that?
As I demonstrated already , CRC is merely a remainder
of division by some polynomial, over GF(2).

In other words: remainder (x*y, poly) = remainder(x, poly) * remainder(y, poly).
All these rules are also work over modulo arithmetic:

#!/usr/bin/env python3
import random
poly=271 # prime number is like irreducible GF(2)polynomial... but any other divisor will work
x=random.randint(1, 10**10)
y=random.randint(1, 10**10)
assert (x*y) % poly == ((x % poly) * (y % poly)) % poly
assert (x+y) % poly == ((x % poly) + (y % poly)) % poly
assert (x-y) % poly == ((x % poly) - (y % poly)) % poly
assert (y-x) % poly == ((y % poly) - (x % poly)) % poly

(the post first published at 20230305.)

List of my other blog posts.

Subscribe to my news feed

Yes, I know about these lousy Disqus ads.
Please use adblocker.
I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.

Please enable JavaScript to view the comments powered by Disqus.