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!
Best Answer
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)$.