I have a linear code $C$ over $\mathbb{F}_7$ with generator matrix
\begin{equation*}
G=\left[\begin{array}{cccccc}
1 & 1 & 1 & 1 & 1 & 1 \\
1 & 3 & 3^2 & 3^3 & 3^4 & 3^5
\end{array}\right]
\end{equation*}
I know that this is a Reed-Solomon code, and I'm trying to find the generator polynomial of $C$ without using this fact. I know that $3$ is a primitive element of $\mathbb{F}_7$, and I've shown that $C$ is a cyclic code, since the shifts of the rows of $G$ are still codewords.
Now I'm stuck, and not sure how to proceed with finding the generator polynomial without somehow making row operations on $G$ and "making it appear" in the standard cyclic form.
Best Answer
To use row operations to convert $G$ to its standard cyclic form looks ok to me.
Elsewhere, notice that this code has $n=6$ and $k=2$, hence $g(x)$ should have degree $n-k=4$. This means that we need to find a codeword $v = u G = (u_1, u_2) G$ that has a zero in its last position and a one in its first position. This amounts to solve
$$ \begin{cases} u_1 \times 1 + u_2 \times 3^5&= u_1 + 5 u_2 &= 0\\ u_1 \times 1 + u_2\times 1 &= u_1 + u_2 &= 1 \end{cases}$$
Solving this we get $u_1=3$, $u_2=5$ , which gives $u=(1,4,6,5,2,0)$, or $g(x)=1+4x+6x^2+5x^3+2x^4$.
Of course, this is not very different from making row operations on $G$.