I recently saw that binary Golay code can be constructed from an irreducible factor of $x^{23}-1$ over $\mathbb{F}_2$; see wiki-constructions.
Since $x^{23}-1$ over $\mathbb{F}_2$ has three factors: one is $x-1$ and other two are of same degree ($11$). Is there any trick to obtain the factorization of $z^{23}-1$ over $\mathbb{F}_2$?
Here of course in general it is difficult to obtain factorization of a general polynomial over a general field; but since this polynomial has been used in some important code, and also it has less number of factors, I was wondering if anybody had invented any trick to find the factorization.
I am not considering the verification that the factors of $x^{23}-1$ given in wiki actually give product equal to $z^{23}-1$; rather, I am concerning, how can we get it? by some trick?
Since this is about algebra of cyclic codes you may be familiar with a piece of theory that can be used here. Namely, the theory of idempotents of the ring $R=\Bbb{F}_2[x]/\langle x^{23}-1\rangle$. An idempotent is a polynomial (or the coset thereof) $e(x)$ such that $e(x)^2\equiv e(x)\pmod{x^{23}-1}$. Each cyclic code $C$ of the prescribed length (here $23$) has its own idempotent $e_C(x)$ with the properties that 1) $e_C(x)\in C$, 2) $e_C(x)p(x)\equiv p(x)$ for every codeword $p(x)$, 3) we get all the words of $C$ as $e_C(x)f(x)\in R$ with $f(x)$ ranging over all polynomials in $\Bbb{F}_2[x]$.
Item 3 means that $e_C(x)$ is a generator of $C$. It is not quite a generator polynomial (in the usual sense) though, because a generator polynomial $g(x)$ has the further property $g(x)\mid x^{23}-1$. The algebra of cyclic codes (check out e.g. van Lint) plays out so that we get a generator for $C$ by calculating $\gcd(e_C(x),x^{23}-1)$.
All this leads up to my main point. If we can find non-trivial idempotents in $R$, then we can find non-trivial factors of $x^{23}-1$. So let us try and figure out when a sum of monomials $$ e(x)=x^{\ell_1}+x^{\ell_2}+\cdots+x^{\ell_k} \qquad(*) $$ for some exponents $0\le\ell_1<\ell_2<\cdots<\ell_k<23$ might be an idempotent of $R$. We see (freshman's dream in characteristic two) that $$ e(x)^2=x^{2\ell_1}+x^{2\ell_2}+\cdots+x^{2\ell_k}. $$ We need to take advantage of the fact that modulo the ideal $x^{23}-1$ the powers $x^\ell$ and $x^m$ are congruent iff $\ell\equiv m\pmod{23}$. In other words, we can reduce the doubled exponents $2\ell_i$ modulo $23$.
Example. Let's find a minimal such set $S$ containing $\ell_1=1$. Such a set must containt $2\cdot1=2$, $2\cdot2=4$, $8,16$, $2\cdot16=32\equiv9$, $2\cdot9=18$, $2\cdot18=36\equiv13$, $2\cdot 13=26\equiv3$, $2\cdot3=6$, $2\cdot 6=12$. Here the circle closes, because $2\cdot12=24\equiv1$ was already included. Therefore $$ e(x)=x+x^2+x^4+x^8+x^{16}+x^9+x^{18}+x^{13}+x^3+x^6+x^{12} $$ is an idempotent of the ring $R$.
We can then, finally, find a non-trivial factor of $x^{23}-1$ by calculating $\gcd(e(x),x^{23}-1)$. Naughtily leaving that to you (a run of Euclid).