How do I find the generator polynomial for a q-ary cyclic code. I know that for a binary cyclic code, a polynomial that divides $x^n - 1$ can be considered as a generator polynomial (e.g. $1 + x + x^3$ divides $x^7 - 1$ and thus $g(x) = 1 + x + x^3$.
But for non-binary cases I am unsure what is a necessary and sufficient condition to find a generator polynomial. Can someone please give an example. I know that for RS codes $g(x) = (x - a_1)(x - a_2)$. But are there other codes as well ?
Also, if $q = 2^m$, then does this constitute as a special case with additional properties?
For instance $\langle (x + 1)(x+2)\rangle$ is a cyclic code over GF$(3)$ of length 6 and dimension 4.
In fact, all cyclic codes of length $n$ over GF$(q)$ are given by the following procedure. Let $$g_1^{k_1}\cdots g_l^{k_l} = x^n - 1$$ be the irreducible factorization of $x^n - 1$ over GF$(q)$. If $C$ is cyclic code of length $n$ then $C = \langle g(x) \rangle$ where $g$ is a combination of $g_i^{l_i}$s.
For the example that I mentioned, what I did is factor $x^6 - 1$ over GF$(3)$, namely, $$x^6 - 1 = (x+1)^3(x+2)^3$$ and then I took some combination of irreducble factors.