A general construction of permutation polynomials of
m
m
the form (x2 + x + δ)i(2 −1)+1 + x over F22m

arXiv:1712.08066v1 [cs.IT] 21 Dec 2017

Libo Wanga , Baofeng Wub,∗
a

College of Information Science and Technology, Jinan University, Guangzhou 510632,
China
b
State Key Laboratory of Information Security, Institute of Information Engineering,
Chinese Academy of Sciences, Beijing 100093, China

Abstract
Recently, there has been a lot of work on constructions of permutation polym
nomials of the form (x2 + x + δ)s + x over the finite field F22m , especially
in the case when s is of the form s = i(2m − 1) + 1 (Niho exponent). In
this paper, we further investigate permutation polynomials with this form.
Instead of seeking for sporadic constructions of the parameter i, we give a
m
m
general sufficient condition on i such that (x2 + x + δ)i(2 −1)+1 + x permutes
F22m , that is, (2k + 1)i ≡ 1 or 2k (mod 2m + 1), where 1 ≤ k ≤ m − 1 is
any integer. This generalizes a recent result obtained by Gupta and Sharma
who actually dealt with the case k = 2. It turns out that most of previous
constructions of the parameter i are covered by our result, and it yields many
new classes of permutation polynomials as well.
Keywords: Finite field, Permutation polynomial, Niho exponent.
1. Introduction
Let q be a power of a prime p, and Fq be the finite field with q elements.
A polynomial f (x) ∈ Fq [x] is called a permutation polynomial (PP) if its
associated polynomial mapping f : c 7→ f (c) from Fq to itself is a bijection.
PPs over finite fields have important applications in cryptography, coding
and combinatorial design. Classical results on properties, constructions and
∗

Corresponding author
Email address: wubaofeng@iie.ac.cn (Baofeng Wu)

Preprint submitted to Finite Fields Appl.

December 22, 2017

applications of PPs may be found in [4, 5]. For some recent advances and
contributions to this area, we refer to [2, 5] and the references therein.
Helleseth and Zinoviev [1] first investigated PPs of the form


1
2
x +x+δ

2ℓ

+x

for the goal of deriving new identities on Kloosterman sums over F2n , where
δ ∈ F2n with Trn1 (δ) = 1, and ℓ = 0 or 1. This motivated Yuan and Ding [10],
Yuan, Ding ,Wang and Pieprzyk [11] to investigate the permutation behavior
of polynomials having the form
k

(xp − x + δ)s + L(x)
over Fpn , where k, s are integers, δ ∈ Fpn and L(x) is a linearized polynomial.
An extension of the above work and some new classes of PPs were found in
[3, 12, 13, 15]. Specially, Tu et al. [8] proposed two classes of PPs over F22m
of the form
m

(x2 + x + δ)s + x

(1)

for some s satisfies either
s(2m + 1) ≡ 2m + 1 (mod 22m − 1)
or
s(2m − 1) ≡ 2m − 1 (mod 22m − 1).
For these exponents, Zeng et al. [14] further investigated the permutation
behavior of the polynomials having the form
(Trnm (x) + δ)s + L(x)
over finite field F2n , where m | n and L(x) = x or Trnm (x) + x, and “Trnm (·)”
is the trace function from F2n to F2m defined by
2m

m

Trnm (x) = x + x2 + x2

n−m

+ · · · + x2

.

Inspired by the specific PPs obtained by Tu et al. in [8], some classes of PPs
with the form (1) over F22m for exponents s satisfying s(2m + 1) ≡ 2m + 1
(mod 22m − 1) or s(2m − 1) ≡ 2m − 1 (mod 22m − 1), were presented in [16, 9].
2

Very recently, Gupta and Sharma [6] further investigated PPs with the
form (1) over F22m , where s = (2m − 1)i + 1 for some i satisfying 5i ≡
1 or 4 (mod 2m + 1). This result is quite interesting since it gives a much
general sufficient condition on permutation property of polynomials of the
form (1) in the Niho exponent case. In this paper, we devote to finding more
m
m
sufficient conditions on the parameter i such that (x2 + x + δ)i(2 −1)+1 + x
permutes F22m . One condition we find is (2k + 1)i ≡ 1 or 2k (mod 2m + 1),
where 1 ≤ k ≤ m − 1 is any integer, which is a direct generalization of Gupta
and Sharma’s result (the case k = 2). However, it turns out that most
of previous sporadic constructions of the parameter i in the literature are
covered by our result, and of course, it yields many new classes of permutation
polynomials as well.
The rest of this paper is organized as follows. In Section 2, some preliminaries needed are presented. In Section 3, we present our main result.
Concluding remarks are given in Section 4.
2. Preliminaries
Let m be an arbitrary positive integer. For each element x in the finite
m
field F22m , we denote x2 by x̄ in analogy with the usual complex conjugation.
Obviously, we have x + x̄ ∈ F2m and xx̄ ∈ F2m . Define the unit circle of F22m
by the set
m
U = {x ∈ F22m : x2 +1 = x̄x = 1}.
Over the field F22m , the so-called Niho exponent [7] s has the form s =
(2 − 1)i + 2j for two integers i and j. In particular, the exponent s =
(2m − 1)i + 1 is called normalized Niho exponent. In this paper, we mainly
focus on PPs with form (1) over F22m with normalized Niho exponent s.
We give some lemmas needed in the following sections.
m

Lemma 2.1. (see [8, Lemma 2]) Let a, b be two elements of F22m . Then the
equation x̄ + ax + b = 0 has solutions in F22m as follows:

āb+b̄
, if aā 6= 1 ,
 a unique solution aā+1
m
2 solutions,
if aā = 1 and āb + b̄ = 0,

no solution,
if aā = 1 and āb + b̄ 6= 0.

Lemma 2.2. (see [8, Lemma 3]) For any θ ∈ F22m \ F2m , the mapping
θ̄+z
Φ : x 7→ θ+z
from F2m to U \ {1} is bijective, where U is the unit circle of
F22m .
3

Lemma 2.3. Let k be a positive integer, and x, y be two elements of F2n .
Then
2k +1

x

+y

2k +1

= (x + y)

2k +1

+

k−1
X

i

k −2i+1 +1

(xy)2 (x + y)2

.

(2)

i=0

Proof. We prove this result by induction on k.
(i) For k = 1, it is easy to verify that (2) holds.
(ii) Assuming that (2) holds for k > 1, we then prove that it also holds
k
for k + 1. Multiplying both sides of (2) by (x + y)2 , we get
2k +1

(x

+y

2k +1

)(x + y)

2k

= (x + y)

2k+1 +1

+

k−1
X

i

k+1 −2i+1 +1

(xy)2 (x + y)2

.

i=0

k

k

Adding x2 y 2 (x + y) to both sides of above equation, we have
2k+1 +1

x

+y

2k+1 +1

= (x + y)

2k+1 +1

+

k
X

i

k+1 −2i+1 +1

(xy)2 (x + y)2

,

i=0

that is to say, (2) holds for k + 1. The proof is finished.
3. PPs with form (3)
In this section, we investigate the permutation behavior of
m

m −1)+1

f (x) = (x2 + x + δ)i(2

+x

(3)

over F22m for any δ ∈ F22m , where i satisfies (2k + 1)i ≡ 1 or 2k (mod 2m + 1)
for 1 ≤ k ≤ m − 1.
In order to simplify the proof of the main result of the present paper, we
firstly give some discussions, which have already been given by Zha et al. in
[16], for the sake of completeness.
2m
If Tr2m
+ x + δ)s + x permutes F22m for any
m (δ) = 0, then f (x) = (x
m
m
exponent s. This is because (x2 +x+δ)s +x = γ yields (x2 +x+δ)s + x̄ = γ̄,
which means x = (γ̄ + γ + δ)s + γ. Therefore, we only need to consider the
case Tr2m
m (δ) 6= 0 in the rest of this paper.
If Tr2m
m (δ) 6= 0, to prove f (x) permutes F22m , it suffices to prove that for
any γ ∈ F22m , the equation
m −1)+1

(x̄ + x + δ)i(2

4

=x+γ

(4)

has at most one solution in F22m .
Let θ = δ + γ + γ̄. Then we have θ + θ̄ = δ + δ̄ = Tr2m
m (δ) 6= 0, and thus
θ 6= 0. Hence x = γ is not a solution of Eq. (4).
Raising both sides of Eq. (4) to the (2m + 1)-th power gives
m +1

(x̄ + x + δ)2

m +1

= (x + γ)2

,

which means
x̄ + x + δ = λ(x + γ)

(5)

for some λ ∈ U, i.e.,
x̄ + (1 + λ)x + δ + λγ = 0.

(6)

Substituting Eq. (5) into Eq. (4), we obtain
λ1−2i (x̄ + γ̄)i + (x + γ)i = 0.

(7)

The number of solutions of Eq. (6) can be determined by Lemma 2.1. We
define two sets as
U1 = {λ ∈ U : (1 + λ̄)(1 + λ) = 1}
and
U2 = {λ ∈ U : (1 + λ̄)(1 + λ) 6= 1}.
U1 and U2 form a disjoint partition of U. It can be verified that
(1 + λ̄)(1 + λ) + 1 = 1 + λ + λ̄ =

1 + λ + λ2
.
λ
m

If λ ∈ U1 , then 1 + λ + λ2 = 0, i.e., λ3 = 1 and λ 6= 1. Note that λ2 +1 = 1
and (3, 2m + 1) = 1 when m is even, therefore, U1 = ∅ for even m.
Now the solutions of Eq. (4) are divided into the following two cases.
Case I. If λ ∈ U1 , Eq. (6) has solutions (2m solutions) if and only if
(1 + λ̄)(δ + λγ) + δ̄ + λ̄γ̄ = 0,
which implies that δ + δ̄ + λ̄(δ + γ̄ + γ) = 0, i.e., θ + θ̄ + (1 + λ)θ = λθ + θ̄ = 0.
Hence, in this case, there is at most one (none, when m is even) λ ∈ U1 and
it must be equal to the fixed value θθ̄ for a given γ.
5

Case II. If λ ∈ U2 , by Lemma 2.1, we can get that Eq. (6) has one
solution
x=

(1 + λ̄)(δ + λγ) + δ̄ + λ̄γ̄
.
(1 + λ̄)(1 + λ) + 1

(8)

Note that λ ∈ U2 is undetermined. Thus, we need further arguments to fix
it. Obviously, Eq. (8) leads to
x+γ =

δ + δ̄ + λ̄(δ + γ + γ̄)
θ + θ̄ + λ̄θ
=
(1 + λ̄)(1 + λ) + 1
1 + λ + λ̄

(9)

and θ + θ̄ + λ̄θ 6= 0. Substituting it into Eq. (7), we obtain a relation between
λ and θ,
λ1−2i (θ + θ̄ + λθ̄)i + (θ + θ̄ + λ̄θ)i = 0.

(10)

To summarize, if we wish to prove the permutation property of f (x), it
desires to prove that there is at most one λ ∈ U such that Eq. (4) has at
most one solution in Case I or Case II.
With the above preparations, based on deeper arguments on Case I and
Case II, we investigate the permutation behavior of polynomials with form
(3) in the following.
3.1. The parity of m and k is different
Theorem 3.1. Let m and k be two positive integers with different parity.
For any δ ∈ F22m , the polynomial
m

m −1)i+1

f (x) = (x2 + x + δ)(2

+x

permutes F22m , where i satisfies (2k + 1)i ≡ 1 (mod 2m + 1).
Proof. We use the notations and arguments given in the above and only
consider the case Tr2m
m (δ) 6= 0. The discussions are divided into two cases
according to the parity of m and k.
(i) m is even and k is odd.
Note that U1 = ∅ under the assumption m is even. So we just need to
consider case II.
6

Case II. Assume λ ∈ U2 = U. Eq. (10) means
λ1−2i (θ + θ̄ + λθ̄)i = (θ + θ̄ + λ̄θ)i .
Raising both sides of the above equation to the (2k + 1)-th power and noting
that (2k + 1)i ≡ 1 (mod 2m + 1), we obtain
k −1

λ2

(θ + θ̄ + λθ̄) = θ + θ̄ + λ̄θ,

which can be simplified as
k +1

k

θ̄λ2

+ (θ + θ̄)λ2 + (θ + θ̄)λ + θ = 0.

(11)

Now we prove that Eq. (11) has at most one solution in U2 . Suppose there
exist λ1 , λ2 ∈ U2 with λ1 6= λ2 such that
k +1

+ (θ + θ̄)λ1 2 + (θ + θ̄)λ1 + θ = 0

k

k +1

+ (θ + θ̄)λ2 2 + (θ + θ̄)λ2 + θ = 0.

θ̄λ1 2

(12)

and
θ̄λ2 2

k

(13)

Adding Eq. (12) and Eq. (13), we get
k +1

θ̄(λ1 2

k +1

+ λ2 2

k

k

) + (θ + θ̄)(λ1 2 + λ2 2 ) + (θ + θ̄)(λ1 + λ2 ) = 0.

By Lemma 2.3, we have
θ̄ (λ1 + λ2 )

2k +1

+

k−1
X

2i

(λ1 λ2 ) (λ1 + λ2 )

2k −2i+1 +1

i=0

k

!

k

+(θ + θ̄)(λ1 2 + λ2 2 ) + (θ + θ̄)(λ1 + λ2 ) = 0.

(14)

k

Dividing both sides of Eq. (14) by (λ1 + λ2 )2 +1 , we get
!


i
k−1
X
(λ1 λ2 )2
1
1
θ̄ 1 +
+ (θ + θ̄)
= 0.
+
2i+1
2k
λ
+
λ
(λ
+
λ
)
(λ
+
λ
)
1
2
1
2
1
2
i=0
Substituting a =
have

1
λ1 +λ2

θ̄ 1 +

m

and b = a2

k−1
X
i=0

(ab)

2i

!

=

λ1 λ2
λ1 +λ2

into the above equation, we



k
+ (θ + θ̄) a + a2 = 0.
7

(15)

Note that a and b may not belong to F2m , but a + b and ab do. Adding Eq.
(15) and its 2m -th power, we get
!
k−1


X
i
k
k
(θ + θ̄) 1 +
(ab)2 + (θ + θ̄) a + b + a2 + b2 = 0.
i=0

Since θ + θ̄ 6= 0, this equation leads to
1+

k−1
X

i

k

k

(ab)2 + a + b + a2 + b2 = 0.

(16)

i=0

Applying Trm
1 (·) on both sides of Eq.(16), we have
!
k−1
X
i
k
k
(ab)2 + a + b + a2 + b2
1+
0 = Trm
1
i=0

m
= Trm
1 (1) + Tr1

k−1
X

(ab)

2i

(ab)

2i

i=0

m
= Trm
1 (1) + Tr1

k−1
X
i=0

!

!


 k
m
2
2k
a
+
b
+ Trm
(a
+
b)
+
Tr
1
1

= Trm
1 (ab)


λ1 λ2
m
= Tr1
(λ + λ2 )2

 1
λ1 /λ2
m
= Tr1
1 + (λ1 /λ2 )2


1
1
m
= Tr1
+
1 + λ1 /λ2 1 + (λ1 /λ2 )2
"
2i 
2i+1 #
m−1
X 
1
1
=
+
1 + λ1 /λ2
1 + λ1 /λ2
i=0

1
1
+
1 + λ1 /λ2 1 + λ2 /λ1
m
(this is because (λ1 /λ2 )2 = λ2 /λ1 since λ1 /λ2 ∈ U)
= 1.
=

This contradiction implies that Eq. (11) has at most one solution in U2 .
Therefore, Eq.(4) has at most one solution in F22m for any γ ∈ F22m .
8

(ii) m is odd and k is even
Case I. Assume λ ∈ U1 . From Eq. (7), we can get
λ1−2i (x̄ + γ̄)i = (x + γ)i .
Since (2k + 1)i ≡ 1 (mod 2m + 1), raising to the (2k + 1)-th power on both
sides leads to
k
λ2 −1 (x̄ + γ̄) = (x + γ).
Note that 3 | (2k − 1) (k is even) and λ3 = 1, the above equation implies
x̄ + x = γ̄ + γ. Substituting it into Eq .(4), we get a unique solution
m −1)i+1

x = (γ̄ + γ + δ)(2

+γ

of Eq .(4). From the discussions before, we note that λ = θ̄θ ∈ U1 is unique.
Case II. Similar to the proof process for Case II of (i), we can also get
Eq. (16)
k−1
X
i
k
k
1+
(ab)2 + a + b + a2 + b2 = 0.
i=0

Applying

Trm
1 (·)

0 = Trm
1

on both sides of it, we get
k−1
X

1+

2i

2k

(ab) + a + b + a

i=0

m
= Trm
1 (1) + Tr1

k−1
X

(ab)

2i

(ab)

2i

i=0

m
= Trm
1 (1) + Tr1

k−1
X
i=0

= Trm
1 (1)
= 1.

!
!

2k

+b

!


 k
m
2
2k
+ Trm
(a
+
b)
+
Tr
a
+
b
1
1

This contradiction implies Eq. (11) has at most one solution in U2 .
We claim that Case I and Case II can not hold simultaneously.
Similar to Case II of (i), we can get Eq. (11)
k +1

θ̄λ2

k

+ (θ + θ̄)λ2 + (θ + θ̄)λ + θ = 0.

9

λ = 1 is not a solution of the above equation, since θ + θ̄ 6= 0. By Lemma 2.2,
z+θ̄
each λ ∈ U2 \{1} can be uniquely expressed as λ = z+θ
for some z ∈ F22m .
Substituting it into Eq. (11) and simplifying, we can get
k +1

(θ + θ̄)z 2

k

k

k

k

+ (θ2 θ̄ + θ̄2 θ)z + (θ2 + θ̄2 )(θ2 + θθ̄ + θ̄2 ) = 0.

(17)

Note that Case I holds meaning that θ2 + θθ̄ + θ̄2 = 0, further, θ3 + θ̄3 = 0.
k
k
k
2k
2k
2k −1
Therefore,
(θ2 + θ̄2 )(θ2 +θθ̄ + θ̄2 ) = 0 and
+ θ̄2 −1 ) =

 θ θ̄ + θ̄ θ = θθ̄(θ

θθ̄ θ3·

2k −1
3

k −1

+ θ̄2

= θθ̄ θ̄3·

2k −1
3

k −1

+ θ̄2

= 0. Consequently, Eq. (17) has

a unique solution z = 0, then λ = θ̄+z
= θ̄θ ∈ U1 , which contradicts the
θ+z
assumption λ ∈ U2 .
Summarizing the discussion of (ii), Eq. (4) has at most one solution.
Combining (i) with (ii), the proof is finished.

Theorem 3.2. Let m, t, i, j be four positive integers, 1 ≤ i, j ≤ 2m , t · i ≡
1 (mod 2m + 1) and t · j ≡ t − 1 (mod 2m + 1). For any δ ∈ F22m , the
polynomial
m
m
f (x) = (x2 + x + δ)(2 −1)i+1 + x
permutes F22m if and only if
m

m −1)j+1

g(x) = (x2 + x + δ)(2

+x

does.
Proof. Adding t · i ≡ 1 (mod 2m + 1) and t · j ≡ t − 1 (mod 2m + 1), we get
t(i + j − 1) ≡ 0 (mod 2m + 1). Note that gcd(t, 2m + 1) = 1, otherwise, the
congruence equation t · i ≡ 1 (mod 2m + 1) has no solution about variable i.
Therefore, 2m + 1 | i + j − 1, and from 1 ≤ i, j ≤ 2m , we get i + j = 2m + 2.
m

f (x) = (x̄ + x + δ)(2 −1)i+1 + x permutes F22m
m
m
m
⇔ (f (x̄))2 = (x̄ + x + δ)((2 −1)i+1)2 + x
m
= (x̄ + x + δ)(2 −1)(1−i)+1 + x
m
m
= (x̄ + x + δ)(2 −1)(2 +2−i)+1 + x
= g(x) permutes F22m .
The proof is completed.

10

Remark 3.1. Let m be a positive integer and t = 2k +1, where 1 ≤ k ≤ m−1.
Let i and j (1 ≤ i, j ≤ 2m ) be two positive integers satisfying (2k + 1)i ≡
1 (mod 2m + 1) and (2k + 1)j ≡ 2k (mod 2m + 1). By Theorem 3.2, for any
δ ∈ F22m , the polynomial
m

m −1)i+1

m

m −1)j+1

f (x) = (x2 + x + δ)(2

+x

permutes F22m if and only if
g(x) = (x2 + x + δ)(2

+x

does.
As immediate consequences of Theorem 3.1 and Remark 3.1, we get the
following five corollaries.
Corollary 3.1. Let m be a positive integer. For any δ ∈ F22m , both the
polynomials
m
m
f (x) = (x2 + x + δ)2(2 −1)+1 + x
and

m

m (2m −1)+1

g(x) = (x2 + x + δ)2

+x

permute F22m .
Proof. Set k = m − 1 in Theorem 3.1. Then (2k + 1) · 2 ≡ 1 (mod 2m + 1),
and the parity of k = m − 1 and m is obviously different. By Theorem 3.1,
f (x) permutes F22m .
Note that when k = m − 1, (2k + 1) · 2m ≡ 2k (mod 2m + 1). By the fact
that f (x) permutes F22m and Remark 3.1, g(x) permutes F22m .
The results in Corollary 3.1 were presented in [8, Theorem 1] and [9,
Theorem3.2(2)].
Corollary 3.2. Let m be an even positive integer. For any δ ∈ F22m , both
the polynomials
m

f (x) = (x2 + x + δ)
and

m

g(x) = (x2 + x + δ)
permute F22m .
11

2m +2 m
(2 −1)+1
3

+x

2(2m +2) m
(2 −1)+1
3

+x

m

Proof. We take k = 1 in Theorem 3.1, then (2k + 1) · 2 3+2 ≡ 1 (mod 2m + 1),
and k = 1 and m have different parity. By Theorem 3.1, f (x) permutes F22m .
m
Note that when k = 1, (2k + 1) · 2(2 3+2) ≡ 2 (mod 2m + 1). From the
fact that f (x) permutes F22m and Remark 3.1, we get that g(x) permutes
F22m .
The results in Corollary 3.2 were presented in [16, Theorem 1] and [9,
Theorem3.2(3)].
Corollary 3.3. Let m be an odd positive integer, i and j be two positive
integers satisfying 5i ≡ 1 (mod 2m +1) and 5j ≡ 4 (mod 2m +1), respectively.
For any δ ∈ F22m , both the polynomials
m

m −1)i+1

m

m −1)j+1

f (x) = (x2 + x + δ)(2
and

g(x) = (x2 + x + δ)(2

+x
+x

permute F22m .
Proof. Set k = 2 in Theorem 3.1, and note that the parity of k and m is
different. By Theorem 3.1, f (x) permutes F22m when 5i ≡ 1 (mod 2m + 1).
Further, by Remark 3.1, g(x) permutes F22m when 5j ≡ 4 (mod 2m + 1).
The results in Corollary 3.3 were also presented in [6, Theorem 3.1 and
3.4]. In fact, the explicit expressions of i and j were obtained in [6], when
m
m+1
m
m ≡ 1 (mod 4), i = 3·2 5 +4 , j = 2 5 +6 ; when m ≡ 3 (mod 4), i = 2 5+2 , j =
2m+2 +8
.
5
Corollary 3.4. Let m be an even positive integer. For any δ ∈ F22m , both
the polynomials
m
m
f (x) = (x2 + x + δ)(2 −1)i+1 + x
and

m

m −1)j+1

g(x) = (x2 + x + δ)(2
permute F22m in
(1) m ≡ 0 (mod
(2) m ≡ 1 (mod
(3) m ≡ 2 (mod

either of the following three cases:
m
m+2
3) i = 2 9 +5 , j = 5·2 9+13 ;
m
m+3
3) i = 2 9+2 , j = 2 9 +16 ;
m+1
m
3) i = 7·2 9 +8 , j = 2 9 +10 .

12

+x

Proof. Note that in either of the above three cases, 9i ≡ 1 (mod 2m + 1) and
9j ≡ 8 (mod 2m + 1). Take k = 3, and note that the parity of k and m is
different. By Theorem 3.1 and Remark 3.1, the conclusions hold.
Corollary 3.5. Let m be an odd positive integer. For any δ ∈ F22m , both the
polynomials
m
m
f (x) = (x2 + x + δ)(2 −1)i+1 + x
and

m

m −1)j+1

g(x) = (x2 + x + δ)(2
permute F22m in
(1) m ≡ 1 (mod
(2) m ≡ 3 (mod
(3) m ≡ 5 (mod
(4) m ≡ 7 (mod

+x

either of the following four cases:
m
m+1
8) i = 11·217+12 , j = 3·2 17 +22 ;
m
m+1
8) i = 15·217+16 , j = 2 17+18 ;
m+4
m
8) i = 2 17+2 , j = 2 17+32 ;
m
m+2
8) i = 5·217+6 , j = 3·2 17 +28 .

Proof. Note that in either of the above four cases, 17i ≡ 1 (mod 2m + 1) and
17j ≡ 16 (mod 2m + 1). Take k = 4 and note that the parity of k and m is
different. By Theorem 3.1 and Remark 3.1, the conclusions hold.
3.2. The parity of m and k is same
When m and k are both odd integers, the congruence equation (2k +1)·i ≡
1 (mod 2m +1) cannot hold for any i, since gcd(2k +1, 2m +1) 6= 1. Therefore,
we only need to consider the case of both m and k are even.
Theorem 3.3. Let m, k be two even positive integers with k | m and
even. For any δ ∈ F22m , the polynomial
m

m −1)i+1

f (x) = (x2 + x + δ)(2

m
k

is

+x

permutes F22m , where i satisfies (2k + 1)i ≡ 1 (mod 2m + 1).
Proof. Similarly to the proof of Theorem 3.1, we can get the equation (Eq.
(16))
k−1
X
i
k
k
(ab)2 + a + b + a2 + b2 = 0.
1+
i=0

Applying

Trm
k (·)

0 = Trm
k

on both sides of the equation, we get
!
k−1
X
i
k
k
(ab)2 + a + b + a2 + b2
1+
i=0

13

k−1
X

m
= Trm
k (1) + Trk

i=0

k−1
X

= Trm
k
=

i=0
m
Tr1 (ab)

=

Trm
1

= 1.



i

(ab)2

!

λ1 λ2
(λ1 + λ2 )2

(ab)

2i

!


 k
m
2
2k
+ Trm
(a
+
b)
+
Tr
a
+
b
k
k



The remainder of this proof is similar to the proof of Theorem 3.1, we omit
the details here.
As immediate consequences of Theorem 3.3 and Remark 3.1, we get the
following two corollaries.
Corollary 3.6. Let 4 | m. For any δ ∈ F22m , both the polynomials
m

2m+1 +3 m
(2 −1)+1
5

m

3·2m +7 m
(2 −1)+1
5

f (x) = (x2 + x + δ)
and

g(x) = (x2 + x + δ)

+x
+x

permute F22m .
m+1

Proof. Let k = 2. Then m/k is even, since 4 | m. Note that (2k + 1) 2 5 +3 ≡
m
1 (mod 2m + 1), (2k + 1) 3·2 5 +7 ≡ 2k (mod 2m + 1). By Theorem 3.3 and
Remark 3.1, the conclusions hold.
Corollary 3.7. Let 8 | m. For any δ ∈ F22m , both the polynomials
m

2m+3 +9 m
(2 −1)+1
17

m

9·2m +25 m
(2 −1)+1
17

f (x) = (x2 + x + δ)
and

g(x) = (x2 + x + δ)

+x
+x

permute F22m .
m+3

Proof. Let k = 4, then m
is even since 8 | m. Note that (2k + 1) 2 17 +9 ≡
k
m
1 (mod 2m + 1), (2k + 1) 9·2 17+25 ≡ 2k (mod 2m + 1). By Theorem 3.3 and
Remark 3.1, the conclusions hold.
14

4. Concluding remarks
m

m

In this paper, we investigate PPs of the form (x2 + x + δ)i(2 −1)+1 + x
over the finite field F22m for i satisfying (2k + 1)i ≡ 1 or 2k (mod 2m + 1),
where 1 ≤ k ≤ m − 1. Most of the previous constructions can be covered
by our results. Besides, many new classes of PPs with the above form are
obtained. Most importantly, we can easily get infinitely many classes of PPs
with the form (3) only through solving the congruence equation (2k + 1) · i ≡
1 or 2k (mod 2m + 1) under some restriction on k and m.
m
m
We summarize all the known PPs of the form f (x) = (x2 +x+δ)(2 −1)i+1 +
x over F22m in Table 1, in which only the last two rows are not covered by our
result. At last, we again emphasis that there is no restriction on δ ∈ F22m in
all the classes.
Acknowledgements
This work is partially supported by the National Natural Science Foundation of China under Grant No. 61502482.
References
[1] T. Helleseth, V. Zinoviev, New kloosterman sums identities over F2m
for all m. Finite Fields Appl. 9 (2) (2003) 187-193.
[2] X. Hou, Permutation polynomials over finite fields − A survey of recent
advances, Finite Fields Appl. 32 (2015) 82-119.
[3] N. Li, T. Helleseth, X. Tang, Further results on a class of permutation
polynomials over finite fields, Finite Fields Appl. 22 (2013) 16-23.
[4] R. Lidl, H. Niederreiter, Finite Fields, second ed., Encyclopedia Math.
Appl., vol. 20, Cambridge University Press, Cambridge, 1997.
[5] G.L. Mullen, D. Panario, Handbook of Finite Fields, Taylor & Francis,
Boca Raton, 2013.
[6] R.Gupta, R.K. Sharma, Further results on permutation polynomials of
m
the form (xp − x + δ)s + x over Fp2m , Finite Fields Appl. 50 (2018)
196-208.

15

Table 1: Known PPs of the form (x2 + x + δ)i(2
m

m
all m

k
m−1

m is even

1

m is odd

2

m is even

3

m is odd

4

4|m

2

8|m

4

all m
m 6≡ 0 (mod 3)

m

−1)+1

i
m
ni ∈ {2, 2 }

+ x over F22m

References
[8] [9], Corollary 3.1
o

m
m
i ∈ 2 3+2 , 2·(2 3 +2)
m+1
m
m ≡ 1 (mod 4), i ∈ { 3·2 5 +4 , 2 5 +6 }
m
m+2
m ≡ 3 (mod 4), i ∈n{ 2 5+2 , 2 5 +8 } o
m
m+2
m ≡ 0 (mod 3), i ∈ 2 9 +5 , 5·2 9+13

n

2m +2 2m+3 +16
,
9
9

o

m ≡ 1 (mod 3), i ∈
n m
o
m+1
m ≡ 2 (mod 3), i ∈ 7·2 9 +8 , 2 9 +10
o
n m
m+1
m ≡ 1 (mod 8), i ∈ 11·217+12 , 3·2 17 +22
n m
o
15·2 +16 2m+1 +18
m ≡ 3 (mod 8), i ∈
, 17
o
n m17
m+4
m ≡ 5 (mod 8), i ∈ 2 17+2 , 2 17+32
o
n m
5·2 +6 3·2m+2 +28
,
m ≡ 7 (mod 8), i ∈
17
o 17
n m+1
m
2
+3 3·2 +7
, 5
i∈
n m+35
o
m
i ∈ 2 17 +9 , 9·2 17+25

[16] [9], Corollary 3.2
[6], Corollary 3.3

Corollary 3.4

Corollary 3.5

Corollary 3.6
Corollary 3.7

i = 2m−1 + 1
i ∈ {2m−2 + 1, 3 · 2m−2 + 1}

k satisfies (2k + 1)i ≡ 1 or 2k (mod 2m + 1)
[7] Y. Niho, Multi-valued cross-correlation functions between two maximal
linear recusive sequences, PhD dissertation, University of Southern,
California, Los Angeles, 1972.
[8] Z. Tu, X. Zeng, Y. Jiang, Two classes of permutation polynomials
m
having the form (x2 + x + δ)s + x. Finite Fields Appl. 31 (2015) 12-24.
[9] L. Wang, B. Wu, Z. Liu, Further results on permutation polynomials
m
of the form (xp − x + δ)s + L(x) over Fp2m , Finite Fields Appl. 44
(2017) 92-112.
16

[9]
[9] [16]

[10] J. Yuan, C. Ding, Four classes of permutation polynomials of F2m ,
Finite Fields Appl. 13 (4) (2007) 869-876.
[11] J. Yuan, C. Ding, H. Wang, J. Pieprzyk, Permutation polynomials of
the form (xp −x+ δ)s + L(x), Finite Fields Appl. 14 (2) (2008) 482-493.
[12] P. Yuan, C. Ding, Further results on permutation polynomials over
finite fields, Finite Fields Appl. 27 (2014) 88-103.
[13] X. Zeng, X. Zhu, L. Hu, Two new permutation polynomials with the
k
form (x2 +x+δ)s +x over F2n , Appl. Algebra Eng. Commun. Comput.
21 (2) (2010) 145-150.
[14] X. Zeng, S. Tian, Z. Tu, Permutation polynomials from trace functions
over finite fields, Finite Fields Appl. 35 (2015) 36-51.
[15] Z. Zha, L. Hu, Two classes of permutation polynomials over finite fields,
Finite Fields Appl. 18 (4) (2012) 781-790.
[16] Z. Zha, L. Hu, Some classes of permutation polynomials of the form
m
(xp − x + δ)s + x over Fp2m , Finite Fields Appl. 40 (2016) 150-162.

17

