# Find the generator polynomial of a cyclic code

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.

• "finding the generator polynomial without somehow making row operations" So you know how to find the generator polynomial making row operations ? And you are not ok with that? Jan 25 at 16:35

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$$.
• We have $g(x)(1-x)(1-3x)=1-x^6$ (which is the zero element in the ring describing 7-ary cyclic codes of length six, so this checks out! +1, of course. Jan 26 at 19:30