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.

  • $\begingroup$ Thanks for the edit dextero4, makes everything much clearer. $\endgroup$ – user116446 Dec 18 '13 at 18:46

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$$

  • $\begingroup$ I may be missing something here, but it seems that this doesn't take into account the multiplication by x^n. $\endgroup$ – user116446 Dec 19 '13 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy