2
$\begingroup$

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,

enter image description here enter image description here

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.

$\endgroup$
18
  • $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Apr 12, 2022 at 18:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Apr 12, 2022 at 18:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Apr 12, 2022 at 21:20
  • 2
    $\begingroup$ 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$) $\endgroup$
    – Bill Dubuque
    Apr 14, 2022 at 20:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Apr 14, 2022 at 20:06

1 Answer 1

Reset to default
1
$\begingroup$

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

Euclidean division of polynomials states:

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .