[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.