0
$\begingroup$

Reading throught page 12 of the PDF http://downloads.bbc.co.uk/rd/pubs/whp/whp-pdf-files/WHP031.pdf, the first paragraph says that:

"(...) the primitive element $\alpha$ is a root of the field generator polynomial (...)"

I think I know the basics concepts of:

  • primitive element of $\alpha$ of a GF
  • field generator polynomial

but I cannot understand how the roots of the latter are connected with the former.

PS: I'm not a mathematician, but an engineer trying to grasp the basics of the Finite Field Theory to understand the Reed Solomon Coding/Decoding.

Sorry if this can be a dumb question. Thanks in advance.

$\endgroup$
1
  • 1
    $\begingroup$ I one tried to answer a somewhat similar question. Not a close match to yours, but somewhat related. $\endgroup$
    – Jyrki Lahtonen
    Feb 24, 2017 at 20:10

1 Answer 1

Reset to default
1
$\begingroup$

What is going on in the background which this paper/book does not seem to be talking about explicitly, is that to form the fields, we are taking the original field and adding some element $x$.

In other words, we consider all polynomials with coefficients in your field. Then, similar to when we look at integers mod some element, we mod this set of polynomials, which mathematicians call a polynomial ring, by some irreducible polynomial $p(x)$. Thus as an example we can form $GF(4)$ by taking $GF(2)=\Bbb Z_2= \Bbb F_2=\{0,1\}$ and taking polynomials over it, writen as ${\Bbb F_2}[x]$. Then we have the irreducible polynomial $p(x)=x^2+x+1$. Then we take the quotient ${\Bbb F_2}[x]/\langle p(x) \rangle$, so that in effect $x^2+x+1=0$ in our new field. Thus the root of our irreducible polynomial, represented by $x$, has been added to our field. This is exactly the primitive element added to form $GF(4)$. Make sense?

$\endgroup$
3
  • $\begingroup$ May you explain more the following, please? "Then we take the quotient F2[x]/⟨p(x)⟩, so that in effect x^2+x+1=0 in our new field. Thus the root of our irreducible polynomial, represented by x, has been added to our field". $\endgroup$
    – Berk7871
    Feb 24, 2017 at 14:13
  • $\begingroup$ It is the same as the integers mod $n$. When you do that $n=0$, $n+1=1$, etc. We do the same thing in the polynomial ring, so $x^2+x+1=0$ in our example. Now consider the elements of this new field. They are polynomials, but again $x^2+x+1=0$. Hence we have $0,1\in {\Bbb F_2}[x]/\langle p(x)\rangle$. Furthermore, we have $x$ and $x+1$ are in our field since they are not multiples of $p(x)$. Note however that $x^2$ is already in our field though, since $x^2=x+1$, and any power of $x$ greater than 2 reduces similarly. Thus our field is $\{ 0, 1, x, x+1\}$. $\endgroup$
    – user416426
    Feb 24, 2017 at 16:58
  • $\begingroup$ The concept that was missing for me is the "extension of a field GF (p)". Your answer augumented by @Jyrki Lahtonen comment and the excellent PDF ocw.usu.edu/Electrical_and_Computer_Engineering/… (specifically pages 16 to 21) help me understand the issue. $\endgroup$
    – Berk7871
    Feb 25, 2017 at 21:28

You must log in to answer this question.

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