I need to understand the following theorem, so i did an example. But i realized that i don't get everything in the finite field theory. can somebody check the example and say where the mistake is?

Thm: Let $q=p^e$ for some positive integer $e$.

a) if $k \geq 2$ is an even integer or $k$ is odd and $q$ is even, then $f_{a,b,k}(x):=ax^q+bx+(x^q-x)^k, a,b \in \mathbb{F}_{q^2}$ with $a+b \in \mathbb{F}^*_q$, permutes $\mathbb{F}_{q^2}$ if and only if $b\not=a^q$.

b) if $k$ and $q$ are odd positive integers, then $f_{a,k}(x):=ax^q+a^qx+(x^q-x)^k, a \in \mathbb{F}^*_{q^2}$ with $a+a^q \not=0$, permutes $\mathbb{F}_{q^2}$ if and only if gcd($k,q-1)=1$.

My example for a): I take $k=2,q=2$. So $k$ is an even integer bigger or equal 2. Now i choose $a$ and $b$, and i think here is my mistake: $a,b \in \mathbb{F}_{q^2}$. That means a,b are polynomials in the form: $a_1+a_2w$ where $a_1,a_2$ are in $\mathbb{F}_2$, hence $a_1,a_2$ are either $0$ or $1$.$w$ is in $\mathbb{F}_{2^2}$, that means w is either $1,x$ or $x^2$.

So I choose: $a=1+x^2, b=1.$

Then i check if $a+b \in \mathbb{F}^*_q$: $a+b=1+1+x^2=2+x^2=x^2$, since we have $q=2$. Therefore $a+b=x^2 \in \mathbb{F}^*_q$.

So i can apply the theorem: $a^q=(1+x^2)^2=1+x^4=1+x \not=b$.

Therefore $f_{a,b,k}$ permutes $\mathbb{F}_{q^2}$.

So I check if this is true:

$f_{a,b,k}(x)=(1+x^2)x^2+x+(x^2-x)^2=x^2+x^4+x+x^4+x^2=x$ since $x \in \mathbb{F}_4.$

Therfore $f_{a,b,k}$ does permutes $\mathbb{F}_{q^2}$.

I hope anybody can help! I appreciate any help!

b) I take $q=k=3$.

$\Rightarrow F_3=\{0,1,2\}$ and $F^*_9=\{1,2,\alpha, 2\alpha, 1+\alpha, 1+2\alpha, 2+\alpha, 2+2\alpha\}.$

So to choose a, i have the condition $a+a^q \not=0$. So for example, i take $a=1$. $\Rightarrow 1+1^2=2 \not=0$.

Since gcd$(3,2)=1$, it follows by the theorem that $f_{1,3}(x)$ permutes $F_9$.

Check: $f_{1,3}(x)=x^3+x+(x^3-x)^3=2x^3+2x.$

$\Rightarrow: f_{1,3}(0)=0 \ (modulo \ 9), f_{1,3}(1)=4 \ (modulo \ 9), f_{1,3}(2)=2 \ (modulo \ 9), f_{1,3}(3)=6 \ (modulo \ 9), f_{1,3}(4)=1 \ (modulo \ 9), f_{1,3}(5)=8 \ (modulo \ 9), f_{1,3}(6)=3 \ (modulo \ 9), f_{1,3}(7)=7 \ (modulo \ 9), f_{1,3}(8)=5 \ (modulo \ 9).$

So it is true!

  • 1
    $\begingroup$ Firstly you seem to be using $x$ with two different meanings. In the definition of $F_{a,b,k}(x)$, $x$ is a variable that takes values in $F_{q^2}$, not a fixed element of $F_{q^2}$. Secondly, the dimension on $F_{q^2}$ over $F_2$ is $2$, not $3$, so elements of $F_{q^2}$ have the form $a + bw$, where $a,b \in F_q$, and $w$ is a fixed element of $F_{q^2}$ (the basis is $1,w$). $\endgroup$
    – Derek Holt
    Commented May 25, 2014 at 12:50
  • $\begingroup$ I'm afraid your attempted example reveals serious misunderstandings about finite fields. I think you should spend some time learning the basics about their construction and various presentations of their elements before you try your hand at grasphing relatively non-trivial constructions of permutation polynomials. I will take a quick look at the case $q=k=2$, but I have this nagging feeling that it may not help you very much. $\endgroup$ Commented May 25, 2014 at 13:33
  • $\begingroup$ thanx both of you! i just edited my example with the input of derek. I know that i have a lot of missunderstandings, so i try to do as much examples as possible. is it right now? $\endgroup$
    – mr_T
    Commented May 25, 2014 at 13:37
  • $\begingroup$ You didn't fully get Derek's point. You still use $a=1+x^2$, but $a$ is supposed to be a constant from $\Bbb{F}_4$. $\endgroup$ Commented May 25, 2014 at 13:58
  • $\begingroup$ It looks like you need to gain familiarity with the constructions and arithmetic of finite fields. I cannot do all that, but this CW question/answer pair I designed for the benefit of our tag wiki may help you a little. $\endgroup$ Commented May 25, 2014 at 14:05

1 Answer 1


Let's look at the case $q=2, k=2$. We seek to get permutations of $\Bbb{F}_4$, so let's first recall that $$\Bbb{F}_4=\{0,1,\alpha,\alpha+1\},$$ where $\alpha$ is a zero of the polynomial $x^2+x+1$. Therefore the multiplication table looks like $\alpha^2=\alpha+1$, $\alpha(\alpha+1)=\alpha^2+\alpha=1$, and $(\alpha+1)^2=\alpha^2+1=(\alpha+1)+1=\alpha$.

The construction calls for a pair of elements $a,b\in \Bbb{F}_4$ such that $a+b\in\Bbb{F}_2^*$. This is very restrictive as $\Bbb{F}_2=\{0,1\}$, so we are forced to choose $a+b=1$. Furthermore the pairs $\{a,b\}=\{\alpha,\alpha+1\}$ are excluded, because we just saw that those two elements are squares of each other. Thus we are left with the two choices $a=0,b=1$ or $a=1,b=0$. Let's do the first one. $$ f_{0,1,2}(x)=ax^2+bx+(x^2+x)^2=x+(x^2+x)^2=x+(x^4+x^2)=x+x^4+x^2. $$ For all $x\in\Bbb{F}_4$ we have $x^4=x$. So as a polynomial function from $\Bbb{F}_4$ to itself $f_{0,1,2}(x)=x^2$ is just the Frobenius automorphism, and hence known to be permutation: $$ f_{0,1,2}:0\mapsto 0,1\mapsto1,\alpha\mapsto \alpha+1,\alpha+1\mapsto \alpha. $$ As another check let's explain what goes wrong, if we don't observe the condition $a\neq b^q$. If we try here $a=\alpha, b=a^2=\alpha+1$, then we get the polynomial $$ f_{\alpha,\alpha+1,2}(x)=\alpha x^2+(\alpha+1)x+(x^2+x)^2=x^4+(\alpha+1)(x^2+x). $$ We see that $f_{\alpha,\alpha+1,2}(0)=0$, but also that $$ f_{\alpha,\alpha+1,2}(\alpha+1)=(\alpha+1)^4+(\alpha+1)([\alpha+1]^2+[\alpha+1])= (\alpha+1)+(\alpha+1)\cdot1=0, $$ so we don't get a permutation in this case.

  • $\begingroup$ thank you so much!!! i understand it! (or at least i hope so) I did for the b) an example by myself! i edit it in the question! $\endgroup$
    – mr_T
    Commented May 25, 2014 at 17:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .