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

EDIT2: typos