Polynomial division with reference to CRC32

113 Views Asked by At

The polynomials we're using will always have coefficients of either 1 or 0.

We have a divisor polynomial which will always remain the same, we'll call this polynomial $D$. We have a dividend polynomial, which is variable, and will be called polynomial $X$.

We'll divide $X$ by $D$ and take the remainder, $R_1$ $$X \equiv R \pmod D $$

We'll then modify $X$ in the following way:

We'll add some terms to it, for example three terms. Before we do this, we'll promote all the existing terms by the number of terms we wish to add. So in this case we'll multiply $X$ by $x^3$. Then we'll add, for example, $x^2 + x + 1$.

Finally we'll divide this modified $X$ (which we'll call $X_1$) by $D$ again, giving us remainder $R_2$.

For example:

$$X \equiv R_1 \pmod D$$ $$x^{32} + x^{14} + x^{12} + x^3 \equiv R_1 \pmod D $$

Terms to add: $x^4 + x^2 + 1$

$$X_1 \equiv R_2 \pmod D $$ $$x^{37} + x^{19} + x^{17} + x^8 + x^4 + x^2 + 1 \equiv R_2 \pmod D$$

What we would like to derive is a formula whereby we can predict $R_2$ given only $R_1, D $and any terms we wish to add to $X$.

Thanks for your time. If I haven't been clear but you still wish to help, please don't hesitate to ask for clarification.

1

There are 1 best solutions below

1
On

Since the $\pmod D\;$ operation is linear, you get from $X_1 = X + Y,\;$ where $Y$ are the additional terms with $R_Y \equiv Y \pmod D$, the relation $$R_2 \equiv R_1 + R_Y \pmod D$$