# Modulo calculation on a polynomial, in NASA tutorial on Reed-Solomon codes

I am reading Geisel's tutorial$$^{\color{red}{\star}}$$ on Reed-Solomon codes, in which a Galois Field is developed. The elements of the field are generated as consecutive powers of $$X$$, modulo an irreducible, primitive polynomial $$F(X)=X^4+X+1$$. From pages 18 and 19,

My question is: Why can $$X^4\mod F(X) = X^4 + X + 1$$ be calculated by '... setting our 4th degree $$F(X)$$ to zero, and obtain the 4-tuple equivalent to $$X^4$$.'?

A few pages later, the same modulo function is performed using a long division on the polynomials, which I understand. But why can this also be done as mentioned above?

The answer is probably obvious, I just don't see it.

$$\color{red}{\star}$$ William A. Geisel, Tutorial on Reed-Solomon Error Correction Coding [PDF], NASA Technical Memorandum 102162, NASA, August 1990.

• We are calculating in the ring $\,\Bbb Z_2[x]/F(x) \,\cong\, \Bbb Z_2[X]\bmod F(x),\,$ i.e. polynomials with coefficients in $\Bbb Z_2$ with the hypothesis that $\,0\equiv F(X)= X^4+X+1,\,$ so $\,X^4\equiv -X-1\equiv X+1,\,$ by $-1\equiv 1,\,$ by $\,2\equiv 0.\,$ Here $X$ denotes a generic root of $F$ (we assume only the ring axioms and that $X$ is a root). It is a special case of a quotient ring construction. Apr 12, 2022 at 18:32
• When $\,F(X) = X^k + H(x)\,$ and $\deg H < k\,$ then we can compute $\,G\bmod F\,$ using $\,X^k\equiv -H(X)\,$ as rewrite rule to continually reduce all powers $\,X^n\,$ till $\,n< 4,\,$ yielding the (unique) least degree polynomial that is congruent to $G$ modulo $F$. This is just as equational form of the longhand division algorithm. These remainders form a complete system of reps of our polynomial ring $\!\bmod F,\,$ just as do $\,0,1,2,\ldots n-1\,$ for $\,\Bbb Z\bmod n.\,$ See here for more on such Euclidean normal forms. Apr 12, 2022 at 18:46
• Here $\alpha$ simply stands for a root of the polynomial $X^4+X+1$. And that's why $\alpha^4+\alpha+1=0$, implying that $\alpha^4=\alpha+1$. From that point on you just calculate with $\alpha$ using the relation to get lower degree polynomials in $\alpha$ as the answer. It is very similar to how you use the relation $(\sqrt 2)^2=2$ when you simplify products like $(2+\sqrt2)(3+7\sqrt2)$ - you use it when it helps! In my discrete log link I denoted this element by $\gamma$ instead, but that's irrelevant. Apr 12, 2022 at 21:20
• It's not "simpler" but rather it is equivalent, i.e. using said rewrite rule $\,X^k \to -H(X)\,$ to eliminate the highest degree monomial $\,X^{k+n}\,$ in $\,G(X)\,$ corresponds precisely to one line (intermediate step) in the (longhand) division algorithm for $\,G(x)\div F(X),\,$ e.g. see the displayed equations here (but swap notation $k\leftrightarrow n$, and $f\leftrightarrow g$) Apr 14, 2022 at 20:00
• As I wrote in my second comment above, this is just the division algorithm performed in equational form, using said rewrite rule to eliminate ("kill") all monomials $\,X^j\,$ in $\,G\,$ that have power $\,j\ge k,\,$ which results in a polynomial $\,\bar G\equiv G\pmod{\!F}\,$ of smaller degree than $F$, so it must be the remainder $\,G\bmod F\,$ (by uniqueness of the remainder), same as in the linked explanation of the division algorithm in my prior comment. Apr 14, 2022 at 20:06

$$X^4 \mod F(X) = X^4 + X + 1$$ can be calculated this way, because this is essentially the (modulo) division algorithm performed in equational form.
"Given two univariate polynomials $$a$$ and $$b ≠ 0$$ defined over a field, there exist two polynomials $$q$$ (the quotient) and $$r$$ (the remainder) which satisfy: $$a = bq + r$$, and $$deg(r) < deg(b)$$.".
The calculation $$X^4 \mod F(X)\ (=X^4 + X + 1) = r$$ (with $$r$$ being the remainder), can be fitted in the Euclidean division as:
• $$a = X^4$$,
• $$b = X^4 + X + 1$$,
• $$q = 1$$ ($$q = 1$$ because this is one first step in a repeated division algorithm),
• $$r = r$$ (the remainder to be calculated).
So $$X^4 = (X^4 + X + 1) ⋅ 1 + r$$. This can be solved to $$r = −X −1$$. After applying the modulo 2 calculation on this result, the result is $$r = X + 1$$.