# How to construct an irreducible polynomial over finite field with a specified order?

The following lemma is well known

Let $f$ be an irreducible polynomail over $\mathbb{F}_q$ of degree $m$ with $f(0)\ne 0$. Then the order of $f$ is equal the order of any rootof $f$ in the multiplicative group group $\mathbb{F}_{q^m}^*$.

My question is, given a positive integer $r$ such that $r \mid q^m-1$, how to construct an irreducible polynomail of order $r$ of degree $m$ over $\mathbb{F}_q$ ?

My Answer: If $r=1$, it is trivial. Denote $s=\frac{q^m-1}{r}$. Let $g$ be a primitive element of $\mathbb{F}_{q^m}$. Then $\alpha=g^s$ is an element of order $r$. Let $n$ be the smallest integer such that $q^n\equiv 1\pmod{r}$. Then define $$f(x)=\prod_{i=0}^{n-1}(x-\alpha^{q^i}).$$ Obviously $f(x)$ is an irreducible polynomail over $\mathbb{F}_q$ of degree $n$ and $n \mid m$. Moreover, $\alpha$ is a root of $f(x)$. So $\text{ord}(f)=\text{ord}(\alpha)=r$. That's $\text{ord}(f) \mid q^n-1$.

We claim that, there are no irreducible polynomail over $\mathbb{F}_q$ of order $r$ of degree differing from $n$, which follows from the conlusion here.

Am I right? Thanks for any replies.

• With $r=1$ we'd find $\alpha=1$ and then $f=(X-1)^m$ is not irreducible for any $m>1$. – ancientmathematician Jan 26 '18 at 9:03
• @ancientmathematician yes, my attempt failed. Any suggestion to construct such a polynomail ? – Zongxiang Yi Jan 26 '18 at 9:08
• Maybe the proof of Theorem 3.4.8 of this book, can be applied for your question. – Amin235 Jan 26 '18 at 12:13
• @Amin235 Thanks. I think I had the answer now. – Zongxiang Yi Jan 26 '18 at 13:37