3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Thanks so much, this is great - I think I kind of understand - I will have another go at the question and see if it sinks in! Could you please explain a bit more how you get the order 24? What is and why do we have $\mathbb F_5^2$? $\endgroup$ – Bernard.Mathews Aug 14 '15 at 5:55
  • $\begingroup$ Here is my definition of a primitive polynomial from my lecture notes: $\alpha \in \mathbb F_q : \mathbb F_q=\{0, 1, \alpha,...,\alpha^q-2 | \alpha^{q-2}=1\}$ does this not include the field? i.e $ \mathbb F_q$? Is this the part you meant? $\endgroup$ – Bernard.Mathews Aug 14 '15 at 5:59
  • 1
    $\begingroup$ Why 24? The field $\mathbb F_{p^n}$ has cardinality $p^n$ meaning that it has 25 elements). One of the elements is 0, the additive identity. The nonzero elements are a cyclic group under multiplication, meaning that they can be represented as $\{1,\alpha,\alpha^2,\cdots, \alpha^{p^n-2}\}$ and $\alpha^{p^n-1}=1=\alpha^0$. The order of an element $\gamma$ is the smallest positive integer $m$ such that $\gamma^m=1$, and so $\alpha$ is an element of order $p^n-1$. The order of $\alpha^k$ is $(p^n-1)/\gcd(p^n-1,k)$ which is a divisor of $p^n-1$. Hence 24, and 1,2,3,4,6,8,12. $\endgroup$ – Dilip Sarwate Aug 14 '15 at 14:09
  • $\begingroup$ $\mathbb F_5^2$ is a two-dimensional vector space: $\mathbb F_{5^2}$ is the finite field of 25 elements. If you need to ask what $\mathbb F_{5^2}$ is at this time with an exam coming up, you really need to go back to basics and put in a lot of study of this material. $\endgroup$ – Dilip Sarwate Aug 14 '15 at 14:13
  • $\begingroup$ Sorry I think you misunderstood me - I know what $F_p$ or $F_{5^2}$ I thought it said $(F_5)^2$ originally- I meant where does the field with 25 elements come from? I know why we are using the field $F_5$ because that is the field the question has specified, but why are we squaring the 5 to get a field of 25 elements? $\endgroup$ – Bernard.Mathews Aug 14 '15 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.