## Cryptology ePrint Archive: Report 2014/659

On the Primitivity of Trinomials over Small Finite Fields

YUjuan Li and Jinhua Zhao and Huaifu Wang

Abstract: In this paper, we explore the primitivity of trinomials over small finite fields. We extend the results of the primitivity of trinomials $x^{n}+ax+b$ over ${\mathbb{F}}_{4}$ \cite{Li} to the general form $x^{n}+ax^{k}+b$. We prove that for given $n$ and $k$, one of all the trinomials $x^{n}+ax^{k}+b$ with $b$ being the primitive element of ${\mathbb{F}}_{4}$ and $a+b\neq1$ is primitive over ${\mathbb{F}}_{4}$ if and only if all the others are primitive over ${\mathbb{F}}_{4}$. And we can deduce that if we find one primitive trinomial over ${\mathbb{F}}_{4}$, in fact there are at least four primitive trinomials with the same degree. We give the necessary conditions if there exist primitive trinomials over ${\mathbb{F}}_{4}$. We study the trinomials with degrees $n=4^{m}+1$ and $n=21\cdot4^{m}+29$, where $m$ is a positive integer. For these two cases, we prove that the trinomials $x^{n}+ax+b$ with degrees $n=4^{m}+1$ and $n=21\cdot4^{m}+29$ are always reducible if $m>1$. If some results are obviously true over ${\mathbb{F}}_{3}$, we also give it.

Category / Keywords: