I am currently reading this paper which shows how to calculate CRC using the instruction PCLMULQDQ. I don’t quite understand the equations in it yet.
- Starting with this one for the definition of crc32:
CRC (M (x)) = xdeg(P(x)) • M(x) mod P(x)
Before reading this paper, I had only ever seen CRC (M (x)) = M(x) mod P (x). Why can xdeg(P(x)) be multiplied with M(x) (and still =CRC) and why do they do it?
- M(x) = D(x) • x^T xor G(x).
Again I do not understand how they derived this equation?
- I also don’t understand why they are using multiplication at all (although this might become clear once I understand 1) and 2).
All CRC implementations I’ve seen so far are basically divisions with or without precomputed values so why do they use multiplication?
In addition, I’d also be very thankful to be pointed towards resources that could help me derive these equations myself in the future.
EDIT: Ive managed to derive 2). Any bitstring M representing a polynomial can be cut into two smaller bitstrings A and B. To add them back together to create M you have to multiply A by x to the power of the number of digits(=T) in B, thereby appending T zeros to the right end of A. Once you’ve done this, you can xor (add in galois field) the two back together, creating M. E.g. M = 10101, A = 101 B = 01 => T = 2; A * x^T = 10100. Xor with B = 10100 xor 01 = 10101 = M