Polynomial arithmetic is often used in the context of Cyclic Redundancy Check (CRC) algorithms. In polynomial arithmetic, the binary representations of numbers are treated as bit-strings, where each bit corresponds to a coefficient in a polynomial.

If it helps, you can think of polynomial arithmetic as binary arithmetic mod 2, with no carries.

What is a Polynomial?

In the context of CRC algorithms, instead of having a divisor, dividend, quotient, and remainder that are viewed as positive integers, each number is viewed as polynomials with binary coefficients.

For example, consider the following polynomial:

1*x^7 + 1*x^6 + 0*x^5 + 0*x^4 + 1*x^3 + 1*x^2 + 0*x^1 + 0*x^0

or, in binary (as an unsigned integer):

0b11001100

Choosing a polynomial isn't something we have to deal with, and probably would warrant many Confluence articles. For our use cases, CRC (and the polynomial) will probably be implemented in the IC that we're using, so the information (and specifics about the CRC implementation) can be found in the datasheet.

Comparing Polynomials

In order to understand polynomial division, we first have to define what it means for a polynomial to be greater than another.

We define that a polynomial X is greater than or equal to polynomial Y if and only if the highest set bit of X is the same or greater than the position of the highest set bit in Y.

Example

Consider the following:

X = 1001, Y = 0101

under this definition,

X >= Y

Example

Likewise, for these polynomials:

X = 1001, Y = 1101

under this definition,

X >= Y

In order to divide two polynomials, we simply perform long-division, using subtraction under polynomial arithmetic.

Operations Under Polynomial Arithmetic

Polynomial Addition

Addition under polynomial arithmetic is defined by the following operation:

Polynomial Subtraction

Subtraction under polynomial arithmetic is defined by the following operation:

At this point, the observant readers will notice that addition and subtraction share the same truth table, and the operation under polynomial arithmetic is equivalent to the XOR operator. In other words, to compute the result of two polynomials in the form:

a + b

or

a - b

we can simply compute

a ^ b

Polynomial Multiplication

Recall from elementary school (or whenever you learned your times tables) that multiplication of two numbers

a * b

can be defined as "a groups of b". Similarly, this holds true in polynomial multiplication.

In other words, the product of 

a * b = a_0 + a_1 + ... + a_b = b_0 + b_1 + ... + b_a

where + is the polynomial addition operator.

Example

        1000
      x 1011
    ---------
        1000  (D0 of 1011 is 1)
       1000.  (D1 of 1011 is 1)
      0000..  (D2 of 1011 is 0)
   + 1000...  (D3 of 1011 is 1)
  -----------
     1011000

Polynomial Division

Polynomial division is very similar to long division. The only difference is that we use our definition of "greater than or equal to" for polynomials, and we perform subtraction under polynomial arithmetic instead.

                     1001000001100
           ________________________
 100101111 ) 100000011010000110000
           - 100101111.,....,,....
           -----------.,....,,
             0001011000,....,,....
            - 000000000,....,,....
            -----------,....,,
              0010110001....,,....
             - 000000000....,,....
             -----------....,,
               0101100010...,,....
              - 100101111...,,....
              -----------...,,
                0010011010..,,....
               - 000000000..,,....
               -----------..,,
                 0100110100.,,....
                - 100101111.,,....
                -----------.,,
                  0000110110,,....
                 - 000000000,,....
                 -----------,,
                   0001101101,....
                  - 000000000,....
                  -----------,
                    0011011011....
                   - 000000000....
                   ------------
                     0110110110...
                    - 100101111...
                    --------------
                      0100110010..
                     - 100101111..
                     ------------
                       0000111010.
                      - 000000000.
                      ------------
                        0001110100 
                       - 000000000
                       ------------
                          01110100


remainder: 0b01110100

Multiples

We say that a polynomial X is a multiple of polynomial Y under polynomial arithmetic, if and only if it is possible to construct polynomial X by XORing in various shifts of Y. Moreover, a polynomial X is not a multiple of polynomial Y if and only if it is not possible to construct polynomial X by XORing various shifts of polynomial Y.