Let me show a toy example of a case, where we can use $\alpha=2$. In the more general finite field we cannot think of $\alpha$ as having a numerical 'value'. I use the finite field $GF(11)$ that is isomorphic to the ring of residue classes of integers modulo 11. I assume that you are at least somewhat familiar with modular arithmetic. This way we can take a look at the use of the generator polynomial in encoding the message without having to worry about the construction of the finite field as well. Also the answer will be of a `reasonable' size :-)
$$
GF(11)=\{0,1,2,3,4,5,6,7,8,9,A=-1\},
$$
where $A$ stands for the residue class of $10\equiv-1\pmod{11}$. The Reed-Solomon codes use
the fact that the multiplicative group of non-zero elements of this (and any other) finite field
is cyclic, i.e. consists of powers of a carefully selected element $\alpha$. Trial and error shows that we can select $\alpha=2$, because $\alpha^0=1$, $\alpha^1=2$, $\alpha^2=4$,
$\alpha^3=8$, $\alpha^4=16= 5$, $\alpha^5=\alpha\cdot \alpha^4=2\cdot 5=10=-1$,
$\alpha^6=2\cdot A=20= 9$, $\alpha^7=2\cdot9=18= 7$, $\alpha^8=2\cdot7=14=3$, and
$\alpha^9=2\cdot3=6$. Note that i) I simply equate any two numbers that are congruent with each other modulo 11, because then the two numbers represent the same element of the field, ii) I won't get any new elements by continuing, because $\alpha^{10}=2\cdot6=12=1=\alpha^0$, so the powers of $\alpha$ repeat starting from the tenth power. A similar thing happens with all the finite fields.
In this toy example I describe the encoding procedure using an RS-code with alphabet $GF(11)$ that has $r=4$ check symbols (IOW the code will have minimum distance $r+1=5$ and
thus be able to correct up to $t=2$ errors, because $2t+1=5$. This type of an RS-code can
carry a message consisting of up to six ($6=11-1-r$) symbols $m_0,m_1,m_2,m_3,m_4,m_5$
that are all elements of the field $GF(11)$. We could agree to use shorter messages, but
this time I go with the maximum. The encoding process expands this message into a longer sequence $c_0,c_1,c_2,\ldots,c_9$ of ten symbols from the field $GF(11)$. In order to make the algebra easier to describe we view such sequences as a polynomials. So let $x$ be an unknown, and write
$$m(x)= m_0+m_1x+m_2x^2+m_3x^3+m_4x^4+m_5x^5$$
and
$$c(x)= c_0+c_1x+c_2x^2+c_3x^3+\cdots+c_9x^9.$$
For the error-correction to work as described, we must make sure that the polynomial $c(x)$ represents a valid codeword, so it has to be a multiple of the generator polynomial
of degree $r=4$
$$
g(x)=(x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)=(x-2)(x-4)(x-8)(x-5).
$$
As an exercise you are invited to verify that after expanding this product and reducing all the coefficients modulo 11 you get
$$
g(x)=x^4+3x^3+5x^2+8x+1.
$$
There are two common ways of turning the message polynomial $m(x)$ to a codeword $c(x)$
that is always divisible by $g(x)$. The simplest way (algebraically) is to declare
$$
c(x)=g(x)m(x).
$$
This is what is known (see e.g. the Wikipedia page) as non-systematic encoding, so e.g. the said Wikipedia page and
Dilip's answer denote this polynomial
$c_{nonsys}(x)$. For example, if the message sequence that you want to encode is
$(m_0,m_1,m_2,m_3,m_4,m_5)=(3,0,0,0,0,1)$, the message polynomial is $m(x)=3+x^5$, and
$$
c_{nonsys}(x)=g(x)m(x)=g(x)(x^5+3)=3 + 2x + 4x^2 + 9x^3 + 3x^4 + x^5 + 8x^6 + 5x^7 +
3x^8 + x^9,
$$
so the encoded message is the sequence $(3,2,4,9,3,1,8,5,3,9)$.
For practical reasons engineers often prefer to use so called systematic encoding. Dilip's answer (linked to above) gives you the following recipe: Compute the polynomial
$x^rm(x)=x^4(x^5+3)=x^9+3x^4$, and then compute the remainder, when you divide this
polynomial with the generator polynomial $g(x)$. The answer is $r(x)=4x+4x^2+x^3$.
Thus the polynomial
$$
c_{sys}(x)=x^4 m(x)-r(x)=x^9+3x^4-x^3-4x^2-4x=7x+7x^2+Ax^3+3x^4+x^9
$$
is also divisible by $g(x)$. This time the encoded sequence is thus $(0,7,7,A,3,0,0,0,0,1)$. The reason why this is called systematic is that you see the
payload message sequence $(3,0,0,0,0,1)$ at the end.
=======================
Added: Constructing finite fields of characteristic two.
Here we need more algebra. The field $GF(256)$ is of characteristic two. In other words, every element $\beta \in GF(256)$ satisfies the relation $\beta+\beta=0$. To give you the idea I first describe, how you get a smaller field $GF(8)$. This is just to save space.
The idea is that we want to list the elements of this field as powers of a special element
$\alpha$ the same way we used powers of two in the earlier example. A field will always have special elements $0,1$, so to get to eight elements we want the field to look like
$$
GF(8)=\{0,1,\alpha,\alpha^2,\alpha^3,\alpha^4,\alpha^5,\alpha^6\}.
$$
In the above example of $GF(11)$ the powers of $\alpha$ started repeating after the tenth power ($2^{10}\equiv 1\pmod{11}$). Here we want the powers to start repeating starting from the seventh ($7=8-1$, $10=11-1$), so we want $\alpha^7=1$. Furthermore, we want to be able to add elements of the field together, like $\alpha^3+\alpha^5$ or $1+\alpha^4$ should be one of the elements. The way to achieve this is to declare that $\alpha$ is a root of certain carefully chosen polynomial equation. This time we choose the equation
$$\alpha^3+\alpha+1=0.$$
IOW, $\alpha$ is a root of the polynomial $p(x)=x^3+x+1$.
How does that help? The idea is that then we can calculate with powers of $\alpha$, and always use that equation $p(\alpha)=0$ to reduce to lower powers of $\alpha$. This is much the same way as when you multiply complex numbers together, you use the equation $i^2=-1$, e.g. $(2+i)(3+i)=6+2i+3i+i^2=6+5i+i^2=6+5i-1=5+5i$. Only this time the equation only begins to help, when we reach the third power. Here
$$
\alpha^3=\alpha^3+0=\alpha^3+p(\alpha)=\alpha^3+\alpha^3+\alpha+1=1+\alpha,
$$
because $\alpha^3+\alpha^3=0$. Let's see what happens, when we reduce the powers of $\alpha$ using this relation. In the last column of the following table I always
list the fully reduced version of that power of $\alpha$.
$$
\eqalign{
\alpha^0&=&&=1,\\
\alpha^1&=&&=\alpha,\\
\alpha^2&=&&=\alpha^2,\\
\alpha^3&=&&=1+\alpha,\\
\alpha^4&=&\alpha\cdot\alpha^3=\alpha(1+\alpha)&=\alpha+\alpha^2,\\
\alpha^5&=&\alpha\cdot\alpha^4=\alpha(\alpha+\alpha^2)=\alpha^2+\alpha^3=\alpha^2+(1+\alpha)&=1+\alpha+\alpha^2,\\
\alpha^6&=&\alpha\cdot\alpha^5=\alpha(1+\alpha+\alpha^2)=\alpha+\alpha^2+\alpha^3=
\alpha+\alpha^2+(1+\alpha)&=1+\alpha^2,\\
\alpha^7&=&\alpha\cdot\alpha^6=\alpha(1+\alpha^2)=\alpha+\alpha^3=\alpha+(1+\alpha)&=1.
}$$
Here the last row was in a way superfluous, but I wanted to show you that this choice of the polynomial $p(x)$ leads to the desired conclusion that the powers of $\alpha$ start repeating after the seventh. Notice how a new line always depends on the preceding one, and how
the relation $\alpha^3=\alpha+1$ is applied as many times as necessary to get rid of all the cubic terms and higher.
Now you should notice that the end results in the last column contain all the quadratic polynomials of the form $b_0+b_1\alpha+b_2\alpha^2$, where all the coefficients $b_i,i=0,1,2$ are bits, i.e. elements of the set $\{0,1\}$. That this worked out in this way is kind of a miracle, but it happened, because we were smart in choosing the polynomial $p(x)$. Notice that $p(x)$ is of degree three, and $8=2^3$. Further notice that we can choose to represent
the elements of $GF(8)$ in two ways: either as a power of $\alpha$ or as a quadratic polynomial of $\alpha$. Which do we use? Depends on what we want to do! If we want to add
two elements of the field, we first switch to the quadratic polynomial form, so for example
$$
\alpha^3+\alpha^5=(1+\alpha)+(1+\alpha+\alpha^2)=(1+1)+(\alpha+\alpha)+\alpha^2=\alpha^2.
$$
On the other hand, if we want to multiply two elements of the field, we simply use the
fact that the powers start repeating after the seventh, so $\alpha^6\cdot\alpha^4=\alpha^{10}=
\alpha^{7}\cdot\alpha^3=1\cdot\alpha^3=\alpha^3$. Or, if the elements are given in the
quadratic polynomial form, then we read the table from right to left e.g.
$$
(1+\alpha)(1+\alpha+\alpha^2)=\alpha^3\cdot\alpha^5=\alpha^8=\alpha\cdot\alpha^7=\alpha.
$$
Observe that addition of two quadratic polynomials
$$
(a_0+a_1\alpha+a_2\alpha^2)+(b_0+b_1\alpha+b_2\alpha^2)=(c_0+c_1\alpha+c_2\alpha^2)
$$
amounts to (because of the $\beta+\beta=0$ rule) bitwise XORing of the bit strings, or
$c_0c_1c_2=(a_0a_1a_2)$^$(b_0b_1b_2)$, if I remember the correct C-notation.
For these reasons I keep two look up tables at hand, when I implement a finite field of characteristic two in a program. One to convert the powers $\alpha^i$ to low degree polynomials, and another to go to the reverse direction.
Ok, so that was $GF(8)$, but you want $GF(256)$, where $256=2^8$. This time the field should look like
$$
GF(256)=\{0,1,\alpha,\alpha^2,\alpha^3,\ldots,\alpha^{254}\}.
$$
Now the powers of $\alpha$ start repeating starting from the $255^{th}$, so $\alpha^{255}=1$.
Instead of quadratic polynomials we now end up using the representation in the form
$$
b_0+b_1\alpha+b_2\alpha^2+\cdots+b_7\alpha^7
$$
in terms of $8$ bits $b_0,b_1,\ldots,b_7$. In other words, a single byte will represent an element of this field in the 'additive' form. How do we build the conversion table? To do that we need a suitable polynomial $p(x)$. This time $p(x)$ must be of degree 8. The most common choice is
$$
p(x)=x^8+x^4+x^3+x^2+1.
$$
The page that you linked to seems to be using this. The replacement rule that we get out of this is $\alpha^8=\alpha^4+\alpha^3+\alpha^2+1$. You can use this relation to get rid of
all the eighth powers (and higher!) of $\alpha$. This time the table would have 255 rows, so I hope that you understand, why I won't reproduce it here. Your link seems to have that table.
For a list of other possible polynomials see this link. They give some further links there, too. The links from your other questions lead to some hopefully useful C-code.
OK, now that I have read your questions more carefully, here is some more
preliminary information. Your Reed-Solomon code has a generator polynomial
of degree $4$ which is not the same as what you call the generator
polynomial, viz., $p(x) = x^3 + x + 1$. In coding theory $p(x)$
would be called the irreducible polynomial used to construct the field.
In this instance, it would more likely be called the primitive
polynomial since its root $a$ is a primitive element of the field, meaning
that all $7$ nonzero elements of the field can be represented as powers of
$a$.
So, what is this generator polynomial (call it $g(x)$) of the Reed-Solomon code?
You might have been given this information as part of the problem, so
look for it. The generator polynomial of a $t$-error-correcting Reed-Solomon
code has the property that $2t$ successive powers of $a$ are roots of
the polynomial. Thus, we have
$$\begin{align*}
g(x) &= (x-a^i)(x-a^{i+1})(x-a^{i+2}\cdots(x-a^{i+2t-1})\\
&= g_{2t}x^{2t} + g_{2t-1}x^{2t-1} + \cdots + g_1 x + g_0
\end{align*}$$
where all the coefficients $g_j$ are necessarily nonzero. Popular
choices for $i$ are $0$ and $1$, but unless you know $g(x)$, it
is not possible to answer the question about which
vectors are valid codewords, except possibly in the general
form "This vector is not a valid codeword for any choice
of $i$, $0 \leq i \leq 6$" which would require a lot more
calculation of the form given below.
Valid codeword polynomials are divisible by the generator polynomial
$g(x)$. So, if you are given the second form of $g(x)$ as
described above, then divide the alleged codeword polynomial
$c(x)$ (which,
for the vector $(c_0, c_1, \ldots, c_6)$,
could be $c(x) = c_0 + c_1x + \cdots + c_6x^6$ or
$c(x) = c_0x^6 + c_1x^5 + \cdots + c_5x + c_6$
depending on the convention used in the document
you are reading) by the generator polynomial $g(x)$ which is given
to you. This is plain polynomial long division as you would
have learned in secondary school except
that you are working over a finite field instead of real numbers. If the remainder is zero, the vector is indeed a codeword; if the remainder is nonzero, it is not a codeword.
On the other hand, if you are given the $4$ roots of $g(x)$ but not the
coefficients $g_j$, then rather than
multiplying out the four factors to get the $g_j$ and then doing
the polynomial division, it is easier to simply
evaluate the alleged codeword polynomial $c(x)$
at the four roots of the generator polynomial (this is called computing the syndrome in
coding theory). If all four evaluations $c(a^i)$, $c(a^{i+1})$,
$c(a^{i+2})$, $c(a^{i+3})$
result in $0$, $c(x)$ is indeed a valid codeword polynomial;
if at at least one evaluation gives a nonzero result, $c(x)$
is not a valid codeword polynomial.
This way of checking can be adapted to determine whether the vector in question
is a codeword in any double-error-correcting Reed-Solomon code. Evaluate
the codeword polynomial at $a^i$ for all $i, 0 \leq i \leq 6$. This is
computing the finite-field discrete Fourier transform which you
mentioned. Then look for $4$ consecutive $0$ values in the sequence
$$c(1), c(a), c(a^2), c(a^3), c(a^4), c(a^5), c(a^6), c(1), c(a), c(a^2).$$
If there are $4$ consecutive $0$ values beginning with $c(a^i), 0 \leq i \leq 6$,
then $c(x)$ is a valid codeword polynomial in the double-error-correcting
Reed-Solomon code with generator polynomial
$$g(x) = (x-a^i)(x-a^{i+1})(x-a^{i+2})(x-a^{i+3}).$$
There may be more than one choice of $i$ for which this holds.
On the other hand, there might not be $4$ consecutive zeroes in which
case you have shown that
$c(x)$ is not a valid codeword polynomial in any double-error-correcting
Reed-Solomon code of length $7$ over the finite field of $8$ elements.
Finally, your question about creating a list of codewords has the
following answer. The codewords are all the multiples of $g(x)$.
So, write out all the $8^3$ polynomials $b(x)$ of degree $2$ or less
(remember that polynomials of degree $2$ have $3$ coefficients, and we
have $8$ choices for each coefficient. The codewords then are
the $8^3$ polynomials $b(x)g(x)$. An easier way is to create
three vectors of length $7$ corresponding to $g(x)$, $xg(x)$ and
$x^2g(x)$ respectively, and then take all possible linear
combinations $b_2(x^2g(x)) + b_1 (xg(x)) + b_0g(x)$.
Best Answer
$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:
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:
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$.