A new class of permutation trinomials constructed from Niho exponents

Abstract

Permutation polynomials over finite fields are an interesting subject due to their important applications in the areas of mathematics and engineering. In this paper, we investigate the trinomial f(x) = x ^(p−1)q+1 + x ^pq − x ^q+(p−1) over the finite field $\mathbb {F}_{q^{2}}$, where p is an odd prime and q = p ^k with k being a positive integer. It is shown that when p = 3 or 5, f(x) is a permutation trinomial of $\mathbb {F}_{q^{2}}$ if and only if k is even. This property is also true for a more general class of polynomials g(x) = x ^{(q+1)l+(p−1)q+1} + x ^{(q+1)l + pq} − x ^{(q+1)l + q+(p−1)}, where l is a nonnegative integer and $\gcd (2l+p,q-1)=1$. Moreover, we also show that for p = 5 the permutation trinomials f(x) proposed here are new in the sense that they are not multiplicative equivalent to previously known ones of similar form.

1 Introduction

Let $\mathbb {F}_{q}$ denote the finite field with q elements and $\mathbb {F}_{q}^{*}=\mathbb {F}_{q}\setminus \{0\}$, where q is a prime power. A polynomial $f(x)\in \mathbb {F}_{q}[x]$ is called a permutation polynomial of $\mathbb {F}_{q}$ if the associated mapping f : c↦f(c) permutes $\mathbb {F}_{q}$. Permutation polynomials were firstly studied by Hermite for the finite prime fields and by Dickson for arbitrary finite fields [19]. They have wide applications in coding theory [14], cryptography [5, 25] and combinatorial designs [3]. For a finite field $\mathbb {F}_{q}$, there are in total q! permutation polynomials of $\mathbb {F}_{q}$, and all of them can be obtained from the Lagrange interpolation. Permutations with a few terms are of particular interest because of the simple algebraic expressions. Especially, permutation binomials and trinomials attracted particular attention [11, 12, 15, 20, 27, 31]. Recent achievements on the study of permutation polynomials were surveyed in [11, 23].

Let p be a prime and k a positive integer. A Niho exponent over the finite field $\mathbb {F}_{p^{2k}}$ is a positive integer d satisfying d ≡ p ^j (mod p ^k − 1) for some nonnegative integer j < k. In the case of j = 0, it is called a normalized Niho exponent. Researches in the past decades demonstrate that Niho exponents are good resources that lead to desirable objects in sequence design [6, 30], coding theory [2, 32] and cryptography [7]. Recently, a lot of permutation trinomials of the form

$$F(x)=x+\lambda_{1} x^{s(p^{k}-1)+1}+\lambda_{2} x^{t(p^{k}-1)+1} $$

(1)

have been proposed, where s and t are two integers, and the coefficients λ ₁ and λ ₂ are restricted to {−1, 1}. For p = 2, Li and Helleseth gave a rather detailed list of known pairs (s,t) and some new pairs such that F(x) is a permutation polynomial of $\mathbb {F}_{2^{2k}}$ [16, 17]. In [8, 21, 28, 34] some permutation trinomials of $\mathbb {F}_{2^{2k}}$ of similar form were also presented. For p = 3, Li et al. in [21] investigated several permutation trinomials of $\mathbb {F}_{3^{2k}}$ of the form (1) and proposed three conjectures, which were later confirmed in [18] and [1]. Very recently, for p = 5, Wu and Li in [29] derived a series of sufficient conditions on s, t, λ ₁ and λ ₂ for F(x) to permute $\mathbb {F}_{5^{2k}}$.

There are also some permutation polynomials constructed from Niho exponents over $\mathbb {F}_{q^{2}}$ with q being a power of an arbitrary prime. Hou in [10] characterized the necessary and sufficient conditions on the coefficients for the polynomial $ax+bx^{q}+x^{2q-1}\in \mathbb {F}_{q^{2}}[x]$ to be a permutation of $\mathbb {F}_{q^{2}}$. In [4], for q≢3 (mod 3), the necessary and sufficient conditions for x + x ^t(q−1)+1 + x ^{−t(q−1)+1} to be a permutation polynomial of $\mathbb {F}_{q^{2}}$ were determined, where t is a positive integer. Let $Tr_{q^{2}/q}(\cdot )$ denote the trace function from $\mathbb {F}_{q^{2}}$ to $\mathbb {F}_{q}$ [19]. Some permutation trinomials of $\mathbb {F}_{q^{2}}$ of the form $x+\gamma Tr_{q^{2}/q}(x^{d})$ were obtained in [13], where $\gamma \in \mathbb {F}_{q}^{*}$ and d is a Niho exponent over $\mathbb {F}_{q^{2}}$.

In this paper, we investigate the permutation property of the following trinomial

$$f(x)=x^{(p-1)q+1}+x^{pq}-x^{q+(p-1)}, $$

(2)

where p is an odd prime and q = p ^k for a positive integer k. It is easily verified that (p − 1)q + 1, pq and q + (p − 1) are Niho exponents over $\mathbb {F}_{p^{2k}}$. We show that for p = 3 or 5, f(x) in (2) is a permutation polynomial of $\mathbb {F}_{p^{2k}}$ if and only if k is even. However, for the case p > 5, such a result may not hold. Furthermore, we prove that the above property is also true for more general polynomials

$$g(x)=x^{(q+1)l+(p-1)q+1}+x^{(q+1)l+pq}-x^{(q+1)l+q+(p-1)}, $$

(3)

where l is a nonnegative integer and $\gcd (2l+p,q-1)=1$. In addition, when p = 5, the permutation polynomials f(x) presented in (2) are shown to be new in the sense that they are not multiplicative equivalent to the permutation polynomials of the form (1) in [4, 9, 10, 13, 18, 21, 22, 29].

The remainder of this paper is organized as follows. Section 2 gives some preliminaries and notation, including some useful lemmas. In Section 3, we give the proofs of our main results. Section 4 is devoted to demonstrating that the permutation trinomials f(x) given in (2) are new when p = 5. Section 5 concludes the study.

2 Preliminaries

Let p be a prime, k a positive integer and q = p ^k. The trace function and the norm function from $\mathbb {F}_{q^{2}}$ to $\mathbb {F}_{q}$ will be denoted by T r(x) and N(x), respectively [19]. Namely,

$$Tr(x)=x+x^{q}\,\,\text{ and }\,\,N(x)=x\cdot x^{q},\,\, x\in\mathbb{F}_{q^{2}}.$$

The unit circle U of $\mathbb {F}_{q^{2}}$ is defined by

$$ U=\{x\,\mid\,x^{q+1}=1,\,\,x\in \mathbb{F}_{q^{2}}\}. $$

(4)

In [16,17,18, 21, 29], in order to prove the permutation property of the trinomials constructed from Niho exponents, the authors mainly used the following lemma, which was proved by Park and Lee in 2001 and reproved by Zieve in 2009.

Lemma 1

[24, 33] Let p be a prime and n a positive integer. Assume that d is a positive integer such that d∣(p ⁿ − 1), $h(x)\in \mathbb {F}_{p^{n}}[x]$ and r > 0is a integer. Then, $x^{r}h(x^{\frac {p^{n}-1}{d}})$ is a permutation of $\mathbb {F}_{p^{n}}$ if and only if

• (i) $\gcd \left (r,\frac {p^{n}-1}{d}\right )=1$ and

• (ii) $x^{r}h(x)^{\frac {p^{n}-1}{d}}$ permutes μ _d , where μ _d is the set of d-th root of unity in $\mathbb {F}_{p^{n}}^{*}$ .

The polynomials constructed from Niho exponents over $\mathbb {F}_{q^{2}}$ can always be rewritten in the form $x^{r}h(x^{\frac {q^{2}-1}{d}})$ with d = q + 1. To determine the permutation property of the polynomials $x^{r}h(x^{\frac {q^{2}-1}{d}})$ constructed from Niho exponents by Lemma 1, the main task is to decide if $x^{r}h(x)^{\frac {q^{2}-1}{d}}$ permutes the unit circle U of $\mathbb {F}_{q^{2}}$. However, sometimes the corresponding polynomial $x^{r}h(x)^{\frac {q^{2}-1}{d}}$ leads to a fractional polynomial with high degree [16,17,18, 21, 26, 29]. It is still a difficult problem in general to verify that $x^{r}h(x)^{\frac {q^{2}-1}{d}}$ permutes U.

Another general method for investigating the permutation property of the polynomials constructed from Niho exponents over $\mathbb {F}_{q^{2}}$ is to concentrate on the subset $\mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$. More specifically, assume that G(x) is a polynomial constructed from Niho exponents over $\mathbb {F}_{q^{2}}$ with coefficients in $\mathbb {F}_{q}$. If we can show that G(x) is a permutation of $\mathbb {F}_{q}$ and a permutation of $\mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$ respectively, then G(x) is a permutation polynomial of $\mathbb {F}_{q^{2}}$. To this end, it is usually required that G(x) has the property $G(\mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q})\subseteq \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$, and the key step in the proof is to prove that G(x) is a permutation of $\mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$. This idea originated from [9] and later was used in [21]. In this paper we will use this idea to prove our main result.

The following lemma is needed in the sequel. Its proof is trivial and is omitted here.

Lemma 2

Let q be a prime power. Denote by T r(x)and N(x)the trace function and the norm function from $\mathbb {F}_{q^{2}}$ to $\mathbb {F}_{q}$, respectively. Then, for any $c\in \mathbb {F}_{q^{2}}$, the set {c,c ^q}is uniquely determined by the pair (T r(c), N(c)).

The following lemma is obtained by direct computations.

Lemma 3

Let q be a prime power, and T r(x)and N(x)be the trace function and the norm function from $\mathbb {F}_{q^{2}}$ to $\mathbb {F}_{q}$, respectively.

• (i) If q = 3^k, then for any $x\in \mathbb {F}_{q^{2}}$,

  $$Tr(x^{2})=Tr^{2}(x)+N(x)\,\,\text{and} \,\,Tr(x^{4})=Tr^{4}(x)-N(x)Tr^{2}(x)-N^{2}(x);$$

• (ii) If q = 5^k, then for any $x\in \mathbb {F}_{q^{2}}$,

  $$Tr(x^{2})=Tr^{2}(x)-2N(x),\,\,Tr(x^{3})=Tr^{3}(x)+2N(x)Tr(x),$$
  $$Tr(x^{4})=Tr^{4}(x)+N(x)Tr^{2}(x)+2N^{2}(x),$$
  $$Tr(x^{6})=Tr^{6}(x)-N(x)Tr^{4}(x)-N^{2}(x)Tr^{2}(x)-2N^{3}(x),$$

  and

  $$Tr(x^{8})=Tr^{8}(x)+2N(x)Tr^{6}(x)-N^{3}(x)Tr^{2}(x)+2N^{4}(x).$$

Proof

We only give the proof of (ii). In Lemma 1 of [29], the expressions for T r(x ²), T r(x ³), T r(x ⁴) and T r(x ⁸) were given while that for T r(x ⁶) was not. Now we compute T r(x ⁶) to illustrate how to obtain the above results. Note that

$$\begin{array}{lll}Tr^{6}(x)&=&(x+x^{q})^{6}\\ &=&(x+x^{q})^{5}(x+x^{q})\\ &=&(x^{5}+x^{5q})(x+x^{q})\\ &=&x^{6}+x^{5+q}+x^{5q+1}+x^{6q}\\ &=&Tr(x^{6})+x^{1+q}\left( x^{4}+x^{4q}\right)\\ &=&Tr(x^{6})+N(x)Tr(x^{4}), \end{array} $$

which implies

$$ Tr(x^{6})=Tr^{6}(x)-N(x)Tr(x^{4}). $$

(5)

Substituting T r(x ⁴) into (5), we get the desired result. □

Lemma 4

Let U be defined as in ( 4 ). We have the following results:

• (i) if q = 3^k, then y ² + 1 = 0has no solution in U if k is even and has two solutions in U otherwise;

• (ii) if q = 5^k, then y ² − y + 1 = 0has no solution in U if k is even and has two solutions in U otherwise.

Proof

(i) Let α be a primitive root of $\mathbb {F}_{q^{2}}$ with q = 3^k. Then, the solutions of y ² = −1 in $\mathbb {F}_{q^{2}}$ are $\pm \alpha ^{\frac {q^{2}-1}{4}}$, which belong to U if and only if q + 1 is divisible by 4. Since q + 1 is divisible by 4 if and only if k is odd, the desired result follows.

(ii) Note that y ² − y + 1 is an irreducible polynomial over $\mathbb {F}_{5}$ because it has no root in $\mathbb {F}_{5}$. Since the degree of y ² − y + 1 is 2, it follows that its two roots belong to $\mathbb {F}_{5^{2}}$. We can rewrite y ² − y + 1 as (y + 2)² − 3. Then, the two roots of y ² − y + 1 in $\mathbb {F}_{5^{2}}$ are $-2\pm \sqrt {3}$, where $\pm \sqrt {3}$ denote the two solutions of x ² = 3 in $\mathbb {F}_{5^{2}}$.

When k is even, $\left (\sqrt {3}\right )^{q}=\sqrt {3}$ since $\sqrt {3}\in \mathbb {F}_{5^{2}}$ and when k is odd, $\left (\sqrt {3}\right )^{q}=\left (\sqrt {3}\right )^{5}=-\sqrt {3}$. Thus, when k is even, we have

$$\begin{array}{lll}\left( -2\pm \sqrt{3}\right)^{q+1}&=&\left( -2\pm \sqrt{3}\right)^{q}\left( -2\pm \sqrt{3}\right)\\ &=&\left( -2\pm \sqrt{3}\right)^{2}\\ &=&2\pm\sqrt{3}, \end{array} $$

which is not equal to 1. When k is odd, we have

$$\begin{array}{lll}\left( -2\pm \sqrt{3}\right)^{q+1}&=&\left( -2\mp \sqrt{3}\right)\left( -2\pm \sqrt{3}\right)\\ &=&4-3\\ &=&1. \end{array}$$

Therefore, when k is odd, $-2\pm \sqrt {3}\in U$. From the above computations, the desired result follows. □

The following lemma is a special case of Exercise 7.4 in [19]. For the reader’s convenience, we include a proof here.

Lemma 5

Let $\mathbb {F}_{q}$ be a finite field of characteristic p. Then, $x^{p}-ux\in \mathbb {F}_{q}[x]$ is a permutation polynomial of $\mathbb {F}_{q}$ if and only if u is not a (p − 1)th power of an element of $\mathbb {F}_{q}^{*}$ .

Proof

Note that x ^p − u x is a p-polynomial over $\mathbb {F}_{q}$, and it is a permutation polynomial of $\mathbb {F}_{q}$ if and only if it only has the root 0 in $\mathbb {F}_{q}$. Thus, x ^p − u x is a permutation polynomial of $\mathbb {F}_{q}$ if and only if x ^p−1 − u has no root in $\mathbb {F}_{q}$. The latter exactly means that u is not a (p − 1)th power in $\mathbb {F}_{q}$. □

3 A new class of permutation trinomials from Niho exponents

In this section, we present our main results about the permutation property of f(x) defined by (2) and that of g(x) defined by (3). The first main result is given in the following theorem.

Theorem 1

Let q = p ^k and f(x) be the trinomial defined by (2). Then for p = 3or 5, f(x)is a permutation polynomial of $\mathbb {F}_{q^{2}}$ if and only if k is even.

Before proceeding with the proof, we first have a general discussion on f(x) and g(x). The three exponents appearing in f(x) are Niho exponents since (p − 1)q + 1 = (p − 1)(q − 1) + p, p q = p(q − 1) + p, and q + (p − 1) = (q − 1) + p. However, the exponents in g(x) may not be Niho exponents. As we will see in the sequel, the permutation property of f(x) and that of g(x) depend on a same condition after utilizing Lemma 1. If we obtain the condition for f(x) to permute $\mathbb {F}_{q^{2}}$, then it is also true for g(x). In addition, a permutation polynomial f(x) of the form (2) is closely related to some permutation polynomial of the form (1). In the next section, we will study the relationship between the permutation trinomials f(x) in Theorem 1 and the previously known ones of the form (1). By comparison, we will show that the permutation polynomials f(x) proposed here are new when p = 5.

In order to prove Theorem 1, the following preparatory lemma is needed.

Lemma 6

Let q = p ^k and f(x) be defined by (2). When p = 3or 5, for any $x\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$, we have $f(x)\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$ if and only if k is even.

Proof

Assume that $x\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$. Note that $f(x)\in \mathbb {F}_{q}$ if and only if

$$x^{(p-1)q+1}+x^{pq}-x^{q+(p-1)}=x^{q+(p-1)}+x^{p}-x^{(p-1)q+1}$$

which is equivalent to

$$ 2x^{q+(p-1)}+x^{p}-x^{pq}-2x^{(p-1)q+1}=0. $$

Dividing the above equation by x ^p, we get

$$ 2x^{q-1}+1-x^{p(q-1)}-2x^{(p-1)(q-1)}=0. $$

(6)

Setting z = x ^q−1, (6) can be rewritten as

$$2z+1-z^{p}-2z^{p-1}=0,$$

which equals

$$ (z-1)(z^{2}+1)=0 $$

(7)

if p = 3, and

$$ (z-1)(z^{2}-z+1)^{2}=0 $$

(8)

if p = 5.

Note that if $x\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$, then z = x ^q−1 ∈ U ∖{1}, where U is defined as in (4). For p = 3, from (7), we can conclude that for any $x\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$, we have $f(x)\in \mathbb {F}_{q}$ if and only if z = x ^q−1 satisfies z ² + 1 = 0. By Lemma 4, if k is even, then z ² + 1 = 0 has no solution in U. Thus, in this case, for any $x\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$, we have $f(x)\notin \mathbb {F}_{q}$, i.e., $f(x)\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$. If k is odd, then z ² + 1 = 0 has two solutions in U ∖{1}, which shows that there are 2(q − 1) elements $x\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$ such that $f(x)\in \mathbb {F}_{q}$. Similarly, for p = 5, we can obtain the same conclusion by (8) and Lemma 4.

From the above discussions, the desired result follows. □

Proof of Theorem 1

Note that in this proof q = p ^k and p is restricted to {3,5}. To prove that f(x) is a permutation of $\mathbb {F}_{q^{2}}$, it suffices to show that for any $c\in \mathbb {F}_{q^{2}}$, f(x) = c has exactly one solution in $\mathbb {F}_{q^{2}}$.

If k is odd, from the proof of Lemma 6, there are 2(q − 1) elements $x\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$ such that $f(x)\in \mathbb {F}_{q}$. On the other hand, note that when $x\in \mathbb {F}_{q}$, then f(x) = x ^p, which is a permutation of $\mathbb {F}_{q}$ since $\gcd (p,q-1)=1$. Therefore, when k is odd, for some $c\in \mathbb {F}_{q}$ there must exist at least two distinct elements $x_{1},\,x_{2}\in \mathbb {F}_{q^{2}}$ such that f(x ₁) = f(x ₂) = c. Thus, f(x) is not a permutation polynomial of $\mathbb {F}_{q^{2}}$ when k is odd.

Next we prove that when k is even, then f(x) is a permutation polynomial of $\mathbb {F}_{q^{2}}$. By the observation that f(x) permutes $\mathbb {F}_{q}$ and Lemma 6, we only need to show that for any $c\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$, f(x) = c has exactly one solution in $\mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$. Let T r(x) and N(x) be defined as in (3). We compute T r(f(x)) and N(f(x)) as follows:

$$\begin{array}{@{}rcl@{}} Tr(f(x))&=&\left( x^{(p-1)q+1}+x^{pq}-x^{q+(p-1)}\right)+\left( x^{(p-1)q+1}+x^{pq}-x^{q+(p-1)}\right)^{q}\\ &=&x^{pq}+x^{p}\\ &=&Tr^{p}(x), \end{array} $$

(9)

and

$$\begin{array}{@{}rcl@{}} N(f(x))\!&=&\!\left( x^{(p-1)q+1}\,+\,x^{pq}\,-\,x^{q+(p-1)}\right)\!\left( x^{q+(p-1)}\,+\,x^{p}\,-\,x^{(p-1)q+1}\right)\\ &=&\!3x^{pq+p}\,+\,\left( x^{(p-1)q+(p+1)}\,+\,x^{(p+1)q+(p-1)}\right)\\ &&\!-\left( x^{(2p-2)q+2}+x^{2q+(2p-2)}\right)\,-\,\left( x^{(2p-1)q+1}\,+\,x^{q+(2p-1)}\right)\\ &=&\!3N^{p}(x)\,+\,N^{p-1}(x)Tr(x^{2})\,-\,N^{2}(x)Tr(x^{2p-4})\,-\,N(x)Tr(x^{2p-2}).\qquad \end{array} $$

(10)

When p = 3 or 5, by Lemma 3, N(f(x)) in (10) can be expressed in terms of T r(x) and N(x) as follows:

$$\arraycolsep=1.2pt\def\arraystretch{1.7} N(f(x))=\left\{\begin{array}{lll} -N(x)Tr^{4}(x)+N^{2}(x)Tr^{2}(x)+N^{3}(x),\,\,\text{for}\,\,p=3,\\ N^{5}(x)+3N^{4}(x)Tr^{2}(x)+N^{3}(x)Tr^{4}(x)\\ ~~~~~~~~~+2N^{2}(x)Tr^{6}(x)-N(x)Tr^{8}(x),\,\,\text{for}\,\,p=5. \end{array}\right. $$

(11)

For any $c\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$, from f(x) = c, we have

$$Tr(f(x))=Tr(c)\,\,\text{and}\,\,N(f(x))=N(c). $$

(12)

In what follows, we will prove that T r(x) and N(x) are uniquely determined by c under the aforementioned conditions that $c\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$, f(x) = c and k is even. We only give the proof for the case p = 5, and for p = 3 it can be proved in the same way. Thus, in the sequel we always assume that q = 5^k.

By (9), (11) and (12), we have

$$ \arraycolsep=1.2pt\def\arraystretch{1.7} \left\{\begin{array}{lll} Tr^{5}(x)=Tr(c),\\ N^{5}(x)+3N^{4}(x)Tr^{2}(x)+N^{3}(x)Tr^{4}(x)+2N^{2}(x)Tr^{6}(x)-N(x)Tr^{8}(x)=N(c). \end{array}\right. $$

(13)

Note that $\gcd (5,q-1)=1$. Thus, from T r ⁵(x) = T r(c), one knows that T r(x) is uniquely determined by c. Therefore, it suffices to show that N(x) is also uniquely determined by c. We consider the following two cases.

Case 1

T r(c) = 0. Then, it follows that T r(x) = 0. By the second equation in (13), we have N ⁵(x) = N(c) and thus N(c) is also uniquely determined by c.

Case 2

T r(c)≠0. Then, T r(x)≠0. For convenience, put

$$ r=\frac{N(x)}{Tr^{2}(x)}\,\,\text{and}\,\,s={N(c)\over Tr^{2}(c)}. $$

(14)

Then, divided by T r ¹⁰(x), the second equation in (13) can be rewritten as

$$ r^{5}+3r^{4}+r^{3}+2r^{2}-r=s $$

or equivalently

$$ (r-2)^{4}(r+1)=s+1. $$

(15)

We claim that s is not equal to − 1. Otherwise, we have N(c) + T r ²(c) = 0, which implies $\left (c^{q}-c\right )^{2}=0$ leading to $c\in \mathbb {F}_{q}$, a contradiction to the assumption $c\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$. Let

$$t=r-2, $$

(16)

then (15) becomes

$$t^{5}+3t^{4}=s+1. $$

(17)

Note that t is not equal to 0 since s is not equal to − 1. Therefore, (17) can be further transformed into

$$\left( \frac{1}{t}\right)^{5}-\frac{3}{s+1}\cdot\frac{1}{t}=\frac{1}{s+1}. $$

(18)

If we can show that $\frac {3}{s+1}$ is not a fourth power in $\mathbb {F}_{q}$, then by (18) and Lemma 5 we can conclude that $\frac {1}{t}$ is uniquely determined by s. Then, from (14) and (16), it follows that N(x) is uniquely determined by c.

Thus, it suffices to show that $\frac {3}{s+1}$ is not a fourth power in $\mathbb {F}_{q}$. To this end, we express $\frac {3}{s+1}$ in terms of c as follows:

$$ \frac{3}{s+1}=\frac{3}{N(c)/Tr^{2}(c)+1}=3\left( 1-\frac{1}{c^{1-q}+c^{q-1}-2}\right). $$

(19)

Since $c\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$ and T r(c)≠0, it follows that c ^q−1 ∈ U ∖{±1}. Let u = c ^q−1. Suppose, on the contrary, that $\frac {3}{s+1}$ is a fourth power in $\mathbb {F}_{q}$. Then, by (19) we have

$$ 3\left( 1-\frac{1}{u+u^{-1}-2}\right)=\omega^{4} $$

(20)

for some $\omega \in \mathbb {F}_{q}$. Note that 3 − ω ⁴≠0. Thus, we can rewrite (20) as

$$ u^{2}+\frac{1+2\omega^{4}}{3-\omega^{4}} u+1=0, $$

which implies

$$ u=\frac{3\omega^{4}+4\pm\sqrt{3}\omega^{2}}{2(3-\omega^{2})}, $$

(21)

where $\pm \sqrt {3}$ denote the two solutions of x ² = 3 in $\mathbb {F}_{5^{2}}$. Note that when k is even, the two solutions of x ² = 3 belong to $\mathbb {F}_{q}$. From (21), it follows that $u\in \mathbb {F}_{q}$, which contradicts to the fact u ∈ U ∖{±1} since $\mathbb {F}_{q}\cap U=\{\pm 1\}$. Therefore, $\frac {1}{s+1}$ is not a fourth power in $\mathbb {F}_{q}$ and the desired result follows.

The discussions in Cases 1 and 2 have shown that for p = 5, under the conditions that $c\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$, f(x) = c and k is even, T r(x) and N(x) are uniquely determined by c. For p = 3, this conclusion can be similarly proved.

It follows from Lemma 2 that if f(x) = c for $c\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$, then the set {x,x ^q} is uniquely determined by c when p ∈{3,5} and k is even. Furthermore, since $f(x^{q})=\left (f(x)\right )^{q}$ and c ^q≠c, only one of {x,x ^q} can satisfy f(x) = c. Therefore, when p ∈{3,5} and k is even, for any $c\in \mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$, f(x) = c has only one solution in $\mathbb {F}_{q^{2}}\setminus \mathbb {F}_{q}$.

From what we have shown above, the desired result follows. □

Corollary 1

Let U be defined as in (4) with q = p ^k and p ∈{3, 5}. Then, the following fractional polynomial

$$ \frac{x+1-x^{p-1}}{x^{p}+x^{p-1}-x} $$

(22)

permutes U if and only if k is even.

Proof

Note that f(x) in (2) can be written as $x^{p}\left (x^{(p-1)(q-1)}+x^{p(q-1)}-x^{q-1}\right )$. Then, by Lemma 1 and Theorem 1, it follows that $x^{p}\left (x^{p-1}+x^{p}-x\right )^{q-1}$ permutes U if and only if k is even, where p ∈{3,5}. Note that if $x^{p}\left (x^{p-1}+x^{p}-x\right )^{q-1}$ permutes U, then it is not equal to zero when x ∈ U. Thus, for each p ∈{3,5}, $x^{p}\left (x^{p-1}+x^{p}-x\right )^{q-1}$ can be written as

$$\frac{x^{p}\left( x^{p-1}+x^{p}-x\right)^{q}}{x^{p-1}+x^{p}-x},$$

which is exactly (22) since x ^q = x ⁻¹ when x ∈ U. □

Based on Lemma 1 and Corollary 1, we obtain our second main result which gives the permutation property of g(x) defined by (3).

Theorem 2

Let q = p ^k with p ∈{3, 5}, and l a nonnegative integer satisfying $\gcd (2l+p,q-1)=1$. Then,

$$g(x)=x^{(q+1)l+(p-1)q+1}+x^{(q+1)l+pq}-x^{(q+1)l+q+(p-1)} $$

is a permutation polynomial of $\mathbb {F}_{q^{2}}$ if and only if k is even.

Proof

We can rewrite g(x) as

$$x^{(q+1)l+p}\left( x^{(p-1)(q-1)}+x^{p(q-1)}-x^{q-1}\right).$$

Note that $\gcd ((q+1)l+p,q-1)=\gcd (2l+p,q-1)=1$. Then, by Lemma 1, g(x) is a permutation polynomial of $\mathbb {F}_{q^{2}}$ if and only if $x^{(q+1)l+p}\left (x^{(p-1)}+x^{p}-x\right )^{q-1}$ permutes U. Since x ^(q+1)l = 1 when x ∈ U, this is equivalent to $x^{p}\left (x^{(p-1)}+x^{p}-x\right )^{q-1}$ permuting U. The desired result follows now from Corollary 1. □

Remark 1

As we have shown in the proofs of Corollary 1 and Theorem 2, f(x) or g(x) is a permutation polynomial of $\mathbb {F}_{q^{2}}$ if and only if $x^{p}\left (x^{(p-1)}+x^{p}-x\right )^{q-1}$ permutes U. This shows that the permutation property of f(x) and that of g(x) depend on a same condition. However, it seems difficult to verify directly whether this condition holds. Thus, in this paper we use a different approach to investigate the permutation property of f(x), and then obtain the permutation property of g(x).

Remark 2

Let f(x) and g(x) be defined by (2) and (3), respectively. The polynomial g(x) contains f(x) as a special case since by taking l = 0, g(x) is reduced to exactly f(x). Note that when p = 2, f(x) = x ^pq and g(x) = x ^{(q+1)l + pq}, which are always permutation polynomials of $\mathbb {F}_{2^{2k}}$ for any positive integer k. For p > 5, Theorems 1 and 2 may not hold. By Magma, we have obtained some numerical results summarized in Table 1.

Table 1 Is f(x) or g(x) a permutation of $\mathbb {F}_{p^{2k}}$

4 A comparison with known related permutation trinomials

In this section, we will compare the permutation polynomials f(x) proposed in Theorem 1 with previously known ones of the form (1). It is straightforward that the composition of two permutation polynomials of the same finite field is also a permutation polynomial. We recall the definition of multiplicative equivalence from [11, 20, 28].

Definition 1

Let q be a prime power, and H(x) and h(x) be two permutation polynomials of $\mathbb {F}_{q}$. H(x) and h(x) are called multiplicative equivalent if there exists an integer 1 ≤ d ≤ q − 2 such that $\gcd (d,q-1)=1$ and H(x) = a h(x ^d) for some $a\in {\mathbb F}_{q}^{*}$.

Next we will determine whether or not the permutation trinomials f(x) given in Theorem 1 are multiplicative equivalent to the previously known ones of the form (1) in [4, 9, 10, 13, 18, 21, 22, 29]. We make some preparations as follows.

Proposition 1

Let f(x)be defined as in (2), and q = p ^k with k being even and p ∈{3, 5}. We have the following results:

• (a) If p = 3, then f(x)is multiplicative equivalent to the following permutation trinomials of $\mathbb {F}_{q^{2}}$ :

  • (i) $f_{1}(x)=x+x^{(2\cdot 3^{k-1}+1)(q-1)+1}-x^{(3^{k-1}+1)(q-1)+1}$ ;

  • (ii) $f_{2}(x)=x+x^{-q+2}-x^{q}$ ;

  • (iii) $f_{3}(x)=x-x^{q}-x^{2q-1}$ ;

• (b) If p = 5, then f(x) is multiplicative equivalent to the following permutation trinomials of $\mathbb {F}_{q^{2}}$ :

  • (i) $f_{1}(x)=x+x^{(4\cdot 5^{k-1}+1)(q-1)+1}-x^{(5^{k-1}+1)(q-1)+1}$ ;

  • (ii) $f_{2}(x)=x+x^{\frac {2q+1}{3}(q-1)+1}-x^{q}$ ;

  • (iii) $f_{3}(x)=x-x^{q}-x^{\frac {q+5}{3}(q-1)+1}$ .

Proof

We only prove the case p = 5. For the case p = 3, the result can be proved in the same way. When p = 5, note that $f_{1}(x)=f(x^{5^{k-1}})$. Thus, f(x) is multiplicative equivalent to f ₁(x). Let d ₁ = (4 ⋅ 5^k−1 + 1)(q − 1) + 1 and d ₂ = (5^k−1 + 1)(q − 1) + 1. When k is even, $\gcd (d_{1},q^{2}-1)=\gcd (d_{2},q^{2}-1)=1$. Then, by extended Euclidean algorithm, we have $d_{1}^{-1}=\frac {2q+1}{3}(q-1)+1$ and $d_{2}^{-1}=\frac {q+5}{3}(q-1)+1$, where d i−1 denotes the inverse of d _i modulo q ² − 1, i = 1,2. Note that f ₂(x) = f ₁(x ^d1−1) and f ₃(x) = −f ₁(x ^d2−1). Therefore, f(x) is multiplicative equivalent to f ₂(x) and f ₃(x). It is easily seen that f ₁(x), f ₂(x) and f ₃(x) are pairwise multiplicative equivalent to each other. □

The following claims are needed.

Claim 1

Recall that the inverse d ⁻¹ of a (normalized) Niho exponent d over $\mathbb {F}_{p^{2k}}$, if it exists, is again a (normalized) Niho exponent, and the product of two (normalized) Niho exponents is also a (normalized) Niho exponent [6].

Let F(x) be a permutation polynomial of $\mathbb {F}_{p^{2k}}$ of the form (1), d ₁ = s(p ^k − 1) + 1 and d ₂ = t(p ^k − 1) + 1. If one of d ₁ and d ₂ is invertible, say d ₁, then λ ₁ F(x ^d1−1) is also a permutation polynomial of the form (1) which is multiplicative equivalent to F(x). This analysis together with Claim 1 gives the following claim.

Claim 2

Let F(x) be a permutation polynomial of $\mathbb {F}_{p^{2k}}$ of the form (1). Then, all the permutation trinomials of the form (1) that are multiplicative equivalent to F(x) are given by λ _i F(x ^di−1) provided $\gcd (d_{i},p^{2k}-1)=1$, i = 1,2.

Claims 1 and 2 together with Proposition 1 give the following claim.

Claim 3

Let f(x) be a permutation polynomial in Theorem 1. If a permutation trinomial of the form (1) is multiplicative equivalent to f(x), then it must be one of f ₁(x), f ₂(x) and f ₃(x) in Proposition 1.

In the sequel, a permutation polynomial F(x) of $\mathbb {F}_{p^{2k}}$ of the form (1) will be denoted by the tuple $\left (\lambda _{1}, s,\lambda _{2}, t\right )$. According to Lemma 1, F(x) is a permutation polynomial of $\mathbb {F}_{p^{2k}}$ if and only if the associated polynomial

$$ x\left( 1+\lambda_{1}x^{s}+\lambda_{2} x^{t}\right)^{p^{k}-1} $$

(23)

permutes the unit circle U. When F(x) is a permutation polynomial of $\mathbb {F}_{p^{2k}}$, (23) can be further written as a fractional polynomial

$$x\frac{1+x^{-s}+x^{-t}}{1+x^{s}+x^{t}} $$

since x ∈ U, which is called the fractional polynomial of F(x). For comparison purposes, we collect all known permutation trinomials of $\mathbb {F}_{3^{2k}}$ and $\mathbb {F}_{5^{2k}}$ of the form (1). We list them in Tables 2 and 3, respectively. To the best of our knowledge, the lists in Tables 2 and 3 are complete.

Table 2 Known permutation trinomials of $\mathbb {F}_{3^{2k}}$ of the form (1) (q = 3^k)

Table 3 Known permutation trinomials of $\mathbb {F}_{5^{2k}}$ of the form (1) (q = 5^k)

Note that the last one in Table 2 is exactly f ₃(x) in Proposition 1 (a)(iii). In [10], Hou determined all permutation trinomials of $\mathbb {F}_{q^{2}}$ of the form $ax+bx^{q}+x^{2q-1}\in \mathbb {F}_{q^{2}}[x]$. When p = 3, according to Theorem A (iv) of [10], − x + x ^q + x ^2q−1 is a permutation polynomial of $\mathbb {F}_{3^{2k}}$ if and only if − 1 is a square of $\mathbb {F}_{3^{k}}^{*}$, which holds if and only if k is even. The permutation polynomial x − x ^q − x ^2q−1 equals $-\left (-x+x^{q}+x^{2q-1}\right )$, and thus its permutation property can be derived from Theorem A (iv) of [10].

According to Tables 2–3, Proposition 1 and Claim 3, we conclude the following result.

Proposition 2

Let f(x) be a permutation polynomial proposed in Theorem 1. When p = 3, f(x)is multiplicative equivalent to the permutation polynomial x − x ^q − x ^2q−1 (or − x + x ^q + x ^2q−1 ) which is contained in Theorem A (iv) of[10]. When p = 5, f(x)is not multiplicative equivalent to any permutation trinomial listed in Table 3.

The above proposition shows that f(x) proposed in Theorem 1 is indeed new when p = 5. When p = 3, the permutation polynomial f(x) proposed in Theorem 1 is multiplicative equivalent to a known one contained in [10]. Nevertheless, the method for proving the permutation property in this paper is different from that in [10].

5 Conclusion

In this paper, we construct a class of permutation trinomials of $\mathbb {F}_{q^{2}}$ with q = 3^k and 5^k. Precisely, for each p ∈{3,5}, we prove that f(x) = x ^(p−1)q+1 + x ^pq − x ^q+(p−1) is a permutation trinomial of $\mathbb {F}_{q^{2}}$ if and only if k is even. This conclusion is also true for more general polynomials g(x) = x ^{(q+1)l+(p−1)q+1} + x ^{(q+1)l + pq} − x ^{(q+1)l + q+(p−1)} with l being a nonnegative integer satisfying $\gcd (2l+p,q-1)=1$. Moreover, when p = 5, we prove that f(x) presented here is not multiplicative equivalent to any known permutation trinomial of the form (1). Numerical experiments show that Theorems 1 and 2 may not hold when p > 5. It would be nice if our construction can be generalized to arbitrary finite field. Namely, the readers are invited to determine the permutation polynomials of $\mathbb {F}_{q^{2}}$ of the form

$$x^{(p-1)q+1}+\lambda_{1}x^{pq}+\lambda_{2}x^{q+(p-1)},$$

where p is a prime, q = p ^k for some positive integer k and $\lambda _{1},\lambda _{2}\in \mathbb {F}_{q}$.