# Polynomial Arithmetic Modulo 2 (CRC Error Correcting Codes)

I'm trying to understand how to calculate CRC (Cyclic Redundancy Codes) of a message using polynomial division modulo 2. The textbook Computer Networks: A Systems Approach gives the following rules for division:

1. Any polynomial $B(x)$ can be divided by a divisor polynomial $C(x)$ if $B(x)$ is of higher degree than $C(x)$.

2. Any polynomial $B(x)$ can be divided once by a divisor polynomial $C(x)$ if $B(x)$ is of the same degree as $C(x)$.

3. The remainder obtained when $B(x)$ is divided by $C(x)$ is obtained by performing the exclusive OR on each pair of matching coefficients.

For example: the polynomial $x^3 +1$ can be divided by $x^3 + x^2 + 1$ because they are both of degree 3. We can find the remainder by XOR the coefficients: $1001 \oplus 1101 = 0100$ and the quotient is obviously 1.

Now, onto long division - and the source of my confusion. The book says: "Given the rules of polynomial division above, the long division operation is much like dividing integers. We see that the division $1101$ divides once into the first four bits of the message $1001$, since they are of the same degree, and leaves the remainder $100$. The next step is to bring down a digit from the message polynomial until we get another polynomial with the same degree as $C(x)$, in this case, $1001$. We calculate the remainder and repeat until the calculation is complete.

So, given an example where I want to divide $010000$ by $1101$ where I know in advance that the quotient is $011$.

       0
________
1101 | 010000  // 1101 does not divide 0100.
1101

01
________
1101 | 010000
1101   // Bring down a digit from the right so we get the same degree as C(x).
----   // 1101 divides into 1000 as they have the same degree.
1010  // Now XOR to find the remainder. Bring down the zero.

011
________
1101 | 010000
1101
----
1010  // Now XOR to find the remainder. Bring down the zero.
1101  // 1101 divides 1010.

011
________
1101 | 010000
1101
----
1010
1101
----
111  // The remainder is 111.


Would this be correct based on the algorithm above?

 010000 1101 1101 111