Finding the Irreducible polynomials which are primitive as part of Coding theory course

Question

I am taking a coding theory course where we have to be able to work out which polynomials over a field $\mathbb F_q$ are irreducible or reducible and then which of the irreducible ones are primitive. I am very confused about primitive polynomials.

I understand irreducible and reducible and I know that to be primitive the polynomial must be irreducible. However, I do not understand how to find out if they are primitive despite having several example questions. I shall put one here with the solution and point out where I am stuck.

This is not a homework question (I have the solutions!) and I have an exam in a week so I would really like a clear explanation of how to do this and what exactly I am doing.

I am aware that in a field $\mathbb F_q$, an element is primitive if it has order $q-1$ (generates the cyclic group) so

$x^{q-1}\equiv 1(\mod q)$

However with polynomials I am completely confused. My lecture notes says the irreducible polynomial over $\mathbb F_q$ that $\alpha$ satisfies if primitive, where $\alpha \in \mathbb F_q : \mathbb F_q=\{0, 1, \alpha,...,\alpha^q-2 | \alpha^{q-2}=1\}$

However I do not understand what this means, and my stressed revision brain is not helping.

Here is an example of a question:

$1a.)$ For $p=5$, decide whether each of the following polynomials is irreducible or not:

We have field $\mathbb F_5=\{0,1,2,-2,-1\}$

$f_1=X^2+2$, This is irreducible as $f_1(0)=2$, $f_1(1)=-2$, $f_1(-1)=-2$, $f_1(2)=-1$ as none are equal to zero (i.e no linear factors) these are all irreducible

$f_2=X^2+X+2$ This is also irreducible as $f_2(0)$, $f_2(1)=-1$, $f_2(-1)=2$, $f_2(2)=-2, f_2(-2)=-1$.

Again no linear factors hence $f_2$ is also irreducible.

$b.)$ For each irreducible polynomial, decide which is primitive

Both $f_1$ and $f_2$ are irreducible

The solution says:

For $f_1$, let $\alpha^2+2=0$, then $\alpha^4=-1$, and $\alpha^8=1$

So i get this so far, the order of alpha is 8, then it says $8 \neq$ 24 so $f_1$ is not primitive. Why 24? why does the order need to be 24? Im confused by this! Please advise..

for $f_2$ it says, let $\beta^2+\beta+2=0$

the divisors of 24 are (again why 24?!) 1,2,3,4,6,8,12

$\beta^2=-\beta - 2$,

$\beta^3=-\beta^2-2\beta=-\beta+2$

$\beta^6=\beta^2-4\beta +4=\beta^2+\beta-1=2$

$\beta^4=\beta^2+4\beta+4=-2\beta+2=-2(\beta -1)$

$\beta^8=-\beta^2+2\beta - 1 = -2\beta+1$

Hence the order of $\alpha$ is not 1,2,3,4,6,8 as $\beta^6=2$ so $\beta^{24}=1$

Hence $\beta$ and $f_2$ are primitive

So I dont really understand any of this answer, if someone could please enlighten me with exactly what is going on I would be extremely grateful!

edit

We have order 24 because, by definition, A polynomial of degree $n$ is primitive if a zero $\alpha \in \mathbb F_{p^n}$ has order $q-1=p^n-1$, ie the smaller $m\leq 1$ such that $\alpha^m=1$ where $m=q-1$

ie the polynomial of degree 2 is primitive if $\alpha \in \mathbb F_{5^2}$ has order $q-1=5^2-1$ ie order is $25-1=24$. So we are looking for polynomials or order 24!

Answer 1

You are mixing up lots of matters in your question.

The polynomials that you are considering have their coefficients in the finite field $\mathbb F_5$ or GF$(5)$ while their roots lie in a larger field $\mathbb F_{5^n}$ where $n$ is the degree of the polynomials ($2$ in this instance).

A polynomial with coefficients in a field $\mathbb F$ is said to irreducible over that field $\mathbb F$ if the polynomial cannot be factored into two (or more) polynomials of smaller degrees with coefficients in that field $\mathbb F$. The polynomial might well factor into polynomials of smaller degree over a larger field, but that is not relevant to irreducubility over the given field. For example, $x^2+1$ is irreducible over the real number field $\mathbb R$ but factors into $(x+i)(x-i)$ over the larger field $\mathbb C$.

Your lecture notes may have a typo, or you may have transcribed them incorrectly into your question above, but the definition of primitive polynomial should mention the field to which the coefficients belong.

$f(x)$, an irreducible polynomial of degree $n$ with coefficients in $\mathbb F_p$, (e.g. $\mathbb F_5$) is called a primitive polynomial over $\mathbb F_p$ (by coding theorists) if the roots of $f(x)$ are primitive elements of the field $\mathbb F_{p^n}$. More generally, $g(x)$, an irreducible polynomial of degree $n$ with coefficients in $\mathbb F_q$, is called a primitive polynomial over $\mathbb F_q$ if its roots are primitive elements of the field $\mathbb F_{q^n}$. Here, of course, $q$ must be a prime $p$ or a prime power $p^m$.

So, let us take up $f_1(x) = x^2+2$ with coefficients in $\mathbb F_5$. Its roots lie in the field $\mathbb F_{5^2}$ which has 25 elements in it, and whose primitive elements have order $24$. If $\alpha$ is a root of $x^2+2$, then $$\alpha^2+2 = 0 \implies \alpha^2=-2 \implies \alpha^8 = (-2)^4 = 1.$$ Thus, $\alpha \in \mathbb F_{5^2}$ is of order $8$ and so $\alpha$ is not a primitive element of $\mathbb F_{5^2}$, and $x^2+2$ is not a primitive polynomial over $\mathbb F_{5}$.

On the other hand, if $\beta$ is a root of $f_2(x) = x^2+x+2$, then your calculations show that none of $\beta, \beta^2, \beta^3, \beta^4, \beta^6, \beta^8$ equal $1$. But, the multiplicative group of $\mathbb F_{5^2}$ is a cyclic group of order $24$ and so the elements of the group can have orders $24$ or a divisor thereof. You have shown that $\beta$ is not an element of order $1,2,3,4,6,8$. The only remaining possibilities are $\beta^{12}=1$ or $\beta^{24} = 1$, and we can eliminate $\beta^{12} = (\beta^6)^2 = 2^2 = 4 \neq 1$ from consideration as well. Hence, $\beta$ is a primitive element of $\mathbb F_{5^2}$ and $x^2+x+2$ (of which $\beta$ is a root), is a primitive polynomial of degree $2$ over $\mathbb F_5$.

Bear in mind that $x^2+x+2$ is neither primitive nor irreducible when viewed as a polynomial with coefficients in $\mathbb F_{5^2}$: over $\mathbb F_{5^2}$, $x^2+x+2$ factors into two linear terms $(x-\beta)(x-\beta^5)$.