A Recursive Construction of Permutation Polynomials over Fq2 with Odd
Characteristic from Rédei Functions
Shihui Fua,b , Xiutao Fenga , Dongdai Linc , Qiang Wangd

arXiv:1712.07890v1 [math.NT] 21 Dec 2017

a

Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy
of Sciences, Beijing, 100190, CHINA
b
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, 100049, CHINA
c
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences,
Beijing, 100093, CHINA
d
School of Mathematics and Statistics, Carleton University, Ottawa, ON K1S 5B6 CANADA

Abstract
In this paper, we construct two classes of permutation polynomials over Fq2 with odd characteristic
from rational Rédei functions. A complete characterization of their compositional inverses is also
given. These permutation polynomials can be generated recursively. As a consequence, we can
generate recursively permutation polynomials with arbitrary number of terms. More importantly,
the conditions of these polynomials being permutations are very easy to characterize. For wide
applications in practice, several classes of permutation binomials and trinomials are given. With
the help of a computer, we find that the number of permutation polynomials of these types is very
large.
Keywords:
Finite fields, Permutation polynomials, Compositional inverse, Redei functions, Dickson
polynomials
2010 MSC: 11T06, 11T55, 05A05
1. Introduction
Let q = pk be the power of a prime number p, Fq be a finite field with q elements, and Fq [x]
be the ring of polynomials over Fq . We call f (x) ∈ Fq [x] a permutation polynomial over Fq if its
associated polynomial mapping f : c 7→ f (c) from Fq to itself is a bijection. It is well known that
every permutation on Fq can be expressed as a permutation polynomial over Fq .
Permutation polynomials over finite fields have been a hot topic of study for many years, and
have applications in coding theory [DH13, Lai07], cryptography[LM83, SH98, RSA78], combinatorial designs [DY06], and other areas of mathematics and engineering. For example, Dickson
permutation polynomials of order five, i.e., D5 (x, a) = x5 + ax3 − a2 x over finite fields, led to a
70-year research breakthrough in combinatorics [DY06], gave a family of perfect nonlinear functions
for cryptography [DY06], generated good linear codes [CDY05, YCD06] for data communication
and storage, and produced optimal signal sets for CDMA communications [DY07], to mention only
a few applications of these Dickson permutation polynomials. For more background material, information about properties, constructions, and applications of permutation polynomials may be found
Email addresses: fushihui@amss.ac.cn (Shihui Fu), fengxt@amss.ac.cn (Xiutao Feng), ddlin@iie.ac.cn
(Dongdai Lin), wang@math.carleton.ca (Qiang Wang)

1

in [LN97, Chapter 7] and [MP13, Chapter 8]. For a detailed survey of open questions and recent
results we refer to see [Hou15].
Recently, Akbary, Ghioca and Wang derived the following useful criterion in studying permutation functions on finite sets. It first appeared in [AGW11] and further developed in [YD11], [YD14],
among others.
Lemma 1 (AGW Criterion). Let A, S and S̄ be finite sets with |S| = S̄ , and let f : A → A,
f¯ : S → S̄, λ : A → S, and λ̄ : A → S̄ be maps such that λ̄◦f = f¯◦λ (see the following commutative
diagram).
A

f

/A

λ



S

f¯



λ̄

/ S̄

If both λ and λ̄ are surjective, then the following statements are equivalent:
(i) f is a bijection from A to A (a permuation over A);
(ii) f¯ is a bijection from S to S̄ and f is injective on λ−1 (s) for each s ∈ S.
For any function f (x) defined over A, Lemma 1 can be viewed piecewisely. Namely, let S =
{s0 , s1 , . . . , sℓ−1 }, then we have

f0 (x),
if x ∈ C0 := λ−1 (s0 );



 ..
..


.
 .
fi (x),
if x ∈ Ci := λ−1 (si );
f (x) =


..
 ..

.
.



fℓ−1 (x), if x ∈ Cℓ−1 := λ−1 (sℓ−1 ),

is a bijection if and only if f¯ is a bijection from S to S̄ and each fi is injective over Ci for 0 ≤ i ≤ ℓ−1.
In particular, if we take A = Fq \ {0} = hγi, ℓs = q − 1, ζ = γ s , and λ = λ̄ = xs , then we obtain
the following commutative diagram.
Fq \ {0}

f

/ Fq \ {0}

xs



S = {1, ζ, . . . , ζ ℓ−1 }

xs
f¯


/ S = {1, ζ, . . . , ζ ℓ−1 }

This special case of AGW criterion was obtained earlier in [NW05] and [Wan07]. Namely, the
cyclotomic mapping polynomial

0,
if x = 0;



r,

A
x
if
x ∈ C0 := hγ ℓ i ⊆ Fq \ {0} = hγi;

0



..
 ..
.
.
P (x) =
(1)
r,
A
x
if
x
∈
Ci := γ i C0 ;

i



..
 ..

.
.



Aℓ−1 xr , if x ∈ Cℓ−1 := γ ℓ−1 C0 ,
is a permutation polynomial over Fq if and only if gcd(r, s) = 1 and f¯ permutes S = {1, ζ, . . . , ζ ℓ−1 }.
Rewriting it in terms of polynomials leads to the following useful criterion.
2

Corollary 1 (Park-Lee [LP97], Wang [Wan07], Zieve [Zie09]). Let q − 1 = ℓs for some positive integers ℓ and s. Then P (x) = xr f (xs ) is a permutation polynomial over Fq if and only if
gcd(r, s) = 1 and xr f (x)s permutes the set µℓ of all distinct ℓ-th roots of unity.
In this paper, we shall employ this corollary to derive two classes of permutation polynomials over
finite fields with odd characteristic. These permutation polynomials can be generated recursively.
Moreover, the conditions of these polynomials being permutations are very easy to characterize. As
a consequence, we can construct permutation polynomials with arbitrary number of terms. Finally,
several classes of permutation binomials and trinomials are given. A complete characterization
of their composiyional inverses is also given. Thus, this provides another two class permutation
polynomials over finite fields with odd characteristic.
The rest of this paper is organized as follows. In the next section, we recall some basic knowledge
about the Rédei functions. In Section 3, two classes of permutation polynomials are presented. As
examples, several classes of permutation binomials and trinomials are also given in this section. The
compositional inverse functions of these permutation polynomials are discussed in Section 4.
2. Rédei Functions
In this section, we present some basic results on the Rédei functions that will be needed in the
sequel. Throughout this paper Fq is the finite field with odd characteristic p having q elements.
Let n be a positive integer, α ∈ Fq2 \ {0}, then we define the following polynomials over Fq2 .
n

Gn (x, α) =

⌊2⌋  
X
n
i=0

2i

αi xn−2i ,

⌋
⌊n
2

X n 
αi xn−2i−1 .
Hn (x, α) =
2i + 1
i=0

The Rédei function is a rational function over Fq2 defined as Rn (x, α) =
that
√
√
(x + α)n = Gn (x, α) + Hn (x, α) α,

Gn (x,α)
Hn (x,α) .

It is easy to check
(2)

and
(x −

√

√
α)n = Gn (x, α) − Hn (x, α) α.

This allows us to generate the polynomials Gn (x, α) and Hn (x, α) recursively,
√
√
Gn (x, α) + Hn (x, α) α = (x + α)n
√
√
= (x + α)n−1 (x + α)
√ 
√
= Gn−1 (x, α) + Hn−1 (x, α) α (x + α)

= (Gn−1 (x, α)x + Hn−1 (x, α)α) + (Gn−1 (x, α) + Hn−1 (x, α)x)

(3)

√
α.

Therefore, we have
G0 (x, α) = 1,

H0 (x, α) = 0,

Gn (x, α) = Gn−1 (x, α)x + Hn−1 (x, α)α,
Hn (x, α) = Gn−1 (x, α) + Hn−1 (x, α)x,
3

(4)

or in the matrix form


 

 
n  
Gn (x, α)
x α Gn−1 (x, α)
x α
1
=
=
.
Hn (x, α)
1 x Hn−1 (x, α)
1 x
0

(5)

There is a simple relationship between Rédei functions and the Dickson polynomials of first
kind Dn (x, a). For a comprehensive survey on Dickson polynomials, we refer the readers to [LN97,
Chapter 7] and [LMT93]. The Dickson polynomial Dn (x, a) over Fq of first kind of degree n in the
indeterminate x and with parameter a ∈ Fq is given as
n

Dn (x, a) =

⌊2⌋
X
i=0



n
n−i
(−a)i xn−2i .
n−i
i

It is well known that for any u1 ∈ Fq , u2 ∈ Fq and positive integer n, by Waring’s formula, it holds
that
un1 + un2 = Dn (u1 + u2 , u1 u2 ).
Then by (2) and (3), we have

√
√
1
(x + α)n + (x − α)n
2
√
√
√ 
√
1
= Dn x + α + x − α, (x + α)(x − α)
2

1
= Dn 2x, x2 − α .
2

Gn (x, α) =

(6)

Moreover, when n is odd, we have


√
√
1 
Hn (x, α) = √ (x + α)n − (x − α)n
2 α

√
√
1 
= √ (x + α)n + (−x + α)n
2 α
√
√
√ 
√
1
= √ Dn x + α − x + α, (x + α)(−x + α)
2 α

√
1
= √ Dn 2 α, α − x2 .
2 α

(7)

In fact, Hn (x, α) is a reversed Dickson polynomial (see more details in [HMSY09]).
The following well-known lemma is needed. Since the proof is short, we include it here for the
reader’s convenience.
Lemma 2. gcd(Gn (x, α), Hn (x, α)) = 1.
√
Proof. Suppose that gcd(Gn (x, α), Hn (x, α)) 6= 1. Then by equation (2), we have (x + α) |
√
√
√
Gn (x, α) and (x + α) | Hn (x, α), which is equivalent to Gn (− α, α) = 0 and Hn (− α, α) = 0.
√
√
√
Thus, Gn (− α, α) − α · Hn (− α, α) = 0.

4

However,
√
√
√
Gn (− α, α) − α · Hn (− α, α)
⌊n
⌋
⌋
⌊n


2 
2 
X
X

√
√
√ n−2i−1
n
n
n−2i
i
=
− α·
α − α
αi − α
2i
2i + 1
i=0

i=0

⌋
⌊n

2 
X
√
√ n−2i−1
√ 2i √ n−2i
√
n
n
+ (− α) ·
(− α) − α
(− α)2i − α
=
2i
2i + 1
i=0
i=0

 n
n
⌊2⌋  
⌊2⌋ 

X
√ n X
n
n

= (− α) 
+
2i
2i + 1
i=0
i=0
√
= (− α)n · 2n 6= 0,
⌋
⌊n
2 

X



which is a contradiction. The conclusion then follows.



3. Two Classes of Permutation Polynomials over Fq2
In this section, we give the constructions of two classes of permutation polynomials derived from
polynomials Hn (x, α) and Gn (x, α). The characterization of being permutations of these constructions are very simple. Besides, from last section we can see that these permutation polynomials
can be generated recursively. This, of course, is an advantage in practical applications. Finally, as
corollaries, we consider some special cases and construct some classes of permutation binomials and
trinomials.
3.1. General Constructions
In this subsection, we give the general constructions of two classes of permutation polynomials
over Fq2 with odd characteristic, which are presented in the next two theorems.
Theorem 1. Suppose n > 0 and m are two integers. Let α ∈ Fq2 satisfy αq+1 = 1. Then polynomial
P (x) = xn+m(q+1) Hn (xq−1 , α)
permutes Fq2 if and only if any one of the following conditions holds
√
1. when α ∈ µq+1 , gcd(n(n + 2m), q − 1) = 1.
√
/ µq+1 , gcd(n + 2m, q − 1) = 1 and gcd(n, q + 1) = 1.
2. when α ∈
Proof. By Corollary 1, it is equivalent to prove that gcd(n + m(q + 1), q − 1) = 1 and
xn+m(q+1) Hn (x, α)q−1
permutes µq+1 . Below we assume that gcd(n+m(q+1), q−1) = 1, or equivalently gcd(n+2m, q−1) =
1. Note that this implies n is odd since q is odd.
Firstly, we show that Hn (x, α) has no roots in µq+1 . Otherwise, suppose that there exist some
b ∈ µq+1 such that Hn (b, α) = 0. Then raising Hn (b, α) to the power of q and substituting bq = b−1
and αq = α−1 into it, we can obtain
 n
q
⌊2⌋ 
⌋
⌊n


2 
X
X
n
n
q
i n−2i−1 

Hn (b, α) =
αb
α−i b−n+2i+1 .
=
2i + 1
2i + 1
i=0

i=0

5

Since n is odd, we can denote 2i′ = n − (2i + 1). The above equation can be reduced to
n

q

Hn (b, α) = b

−n − n−1
2

α

⌊2⌋ 

X
n

i′ =0

2i′

′

′

αi bn−2i = b−n α−

n−1
2

Gn (b, α).

(8)

This implies that Gn (b, α) = 0, which contradict to Lemma 2. Thus, Hn (x, α) has no roots in
µq+1 , and similarly, Gn (x, α) has no roots in µq+1 as well. Hence, we have Hn (x, α) ∈ F∗q2 for any
x ∈ µq+1 . It then implies that xn+m(q+1) Hn (x, α)q−1 ∈ µq+1 for any x ∈ µq+1 . In the following, we
show that xn+m(q+1) Hn (x, α)q−1 , or equivalently xn Hn (x, α)q−1 is injective over µq+1 .
Suppose that there exist x, y ∈ µq+1 such that xn Hn (x, α)q−1 = y n Hn (y, α)q−1 , then by (8), we
can derive that
xn Hn (x, α)q−1 = xn

n−1 Gn (x, α)
Hn (x, α)q
= α− 2
.
Hn (x, α)
Hn (x, α)

(9)

So xn Hn (x, α)q−1 = y n Hn (y, α)q−1 if and only if
Gn (y, α)
Gn (x, α)
=
.
Hn (x, α)
Hn (y, α)

(10)

√
α to the both sides of equation (10), then by (2), we can get
√
√
(y + α)n
(x + α)n
=
.
(11)
Hn (x, α)
Hn (y, α)
√
Similarly, Adding − α to the both sides of the equation (10), then by (3), we can get
√
√
(x − α)n
(y − α)n
=
.
(12)
Hn (x, α)
Hn (y, α)
√
The remaining proof is divided into the following two cases depending on whether α ∈ µq+1 or
not.
√
√
√
√
1. α ∈ µq+1 . Suppose x = α, then by (12), we must have y = α = x. The case of x = − α
√
√
is identical. In the following, we always assume that x 6= ± α and y 6= ± α. By equations
(11) and (12),


√ n
√ n
x− α
x+ α
Hn (x, α)
√
√
=
=
,
Hn (y, α)
y+ α
y− α
Adding

or equivalently,


Since

√

√ n
√ n 
y+ α
x+ α
√
√
=
.
x− α
y− α

√
α ∈ µq+1 , we have ( α)q =



√1 .
α

(13)

Then

√ q−1 
√ 
√ q 
x+ α
x− α
x+ α
√
√
√
=
=
x− α
x− α
x+ α

1
x
1
x

+
−

√1
α
1
√
α



√ 
x− α
√
= −1.
x+ α

This is to say,



√ q−1
√ q−1
y+ α
x+ α
√
√
= −1 =
.
x− α
y− α
6

(14)

Finally, it is easy
to see√that xn Hn (x, α)q−1 is injective over µq+1 if and only if x = y,
√
x+√α
√α . By equations (13) and (14), this is possible if and only if
or equivalently x− α = y+
y− α
gcd(n, q − 1) = 1.
√
√
√
/ µq+1 . Then x 6= ± α and y 6= ± α. We still have the following equation
2. α ∈

√ n 
√ n
x+ α
y+ α
√
√
=
.
(15)
x− α
y− α
Note that


√

√
α∈
/ µq+1 , we have ( α)q = − √1α . Then

√ q 
√ 
√ q+1 
x+ α
x+ α
x+ α
√
√
√
=
=
x− α
x− α
x− α

1
x
1
x

−
+

√1
α
√1
α



√ 
x+ α
√
= −1.
x− α

This is to say,



√ q+1
√ q+1
x+ α
y+ α
√
√
= −1 =
.
x− α
y− α

(16)

√
Similarly as the case √of α ∈√ µq+1 , xn Hn (x, α)q−1 is injective over µq+1 if and only if
x+√α
√α . By equations (15) and (16), this is possible if and only
= y+
x = y, or equivalently x−
α
y− α
if gcd(n, q + 1) = 1.
The proof is now completed.



Remark 1. It is worth noticing that in [Zie13], the author gave two classes of permutation polynomials over Fq2 by exhibiting classes of low-degree rational functions over Fq2 . The permutation
polynomials they exhibited can be also represented by Rédei functions. The first class of permutation
polynomials is given as follows.

xn+m(q+1) · (γxq−1 − β)n − γ(xq−1 − γ q β)n ,

where β, γ ∈ Fq2 satisfy β ∈ µq+1 and γ ∈
/ µq+1 . In fact, we can easy verify that the construction in
Theorem 1 is different from the construction presented by Zieve in [Zie13]. To see this, by equations
(2) and (3), we can obtain
√
√
(x + α)n − (x − α)n
√
Hn (x, α) =
.
2 α
Therefore, the permutation polynomial constructed in Theorem 1 can be presented in the following
form

√
√
(xq−1 + α)n − (xq−1 − α)n
n+m(q+1)
√
.
x
·
2 α
A direct observation show that the two constructions are distinct. We can also check that the construction in Theorem 1 is also distinct from the second class of permutation polynomials constructed
by Zieve in [Zie13].
If we replace Hn (x, α) by Gn (x, α) in Theorem 1, we can obtain another class of permutation
polynomials over Fq2 . Since the proof is almost identical to the proof of Theorem 1, we present
directly the results as follows and omit the proof.
7

Theorem 2. Suppose n > 0 and m are two integers. Let α ∈ Fq2 satisfy αq+1 = 1. Then polynomial
P (x) = xn+m(q+1) Gn (xq−1 , α)
permutes Fq2 if and only if any one of the following conditions holds
√
1. when α ∈ µq+1 , gcd(n(n + 2m), q − 1) = 1.
√
2. when α ∈
/ µq+1 , gcd(n + 2m, q − 1) = 1 and gcd(n, q + 1) = 1.
Remark 2. For a given odd prime power q and an integer m, the number of n which satisfies the
conditions in Theorem 1 and 2 is very large. For instance, when q = 3k , 2 ≤ k ≤ 10 and m = 0,
with the help of a computer, we find that nearly half of the integers in the range [1, q − 1] satisfy the
condition gcd(n(n + 2m), q − 1) = 1.
3.2. Permutation Binomials and Trinomials
From last subsection, for any odd n, we can construct or generate recursively permutation polynomials with n+1
2 terms over Fq 2 with odd characteristic. But for particular interesting, permutation polynomials with few terms, especially binomials and trinomials, over finite fields are an active
research due to their simple algebraic forms, additional extraordinary properties and their wide
applications in many areas of science and engineering. Therefore, in this subsection, we consider
some special cases. Some permutation binomials and trinomials are then given.
Let γ be a primitive element of Fq2 , then µq+1 = hγ q−1 i. An element α ∈ µq+1 can be represented
√
as α = γ l(q−1) , 0 ≤ l ≤ q, and α ∈ µq+1 if and only if l is even. Then by the recursive relations
(4) or (5), we have
G3 (x, α) = x3 + 3αx,
and
H3 (x, α) = 3x2 + α.
By Theorem 1 and 2, we obtain the following permutation binomials over Fq2 . Here we may
suppose that 3 ∤ q, otherwise, the polynomials constructed by G3 (x, α) and H3 (x, α) will become
the monomials, which are permutations over Fq2 if and only if the exponent d is coprime with q 2 − 1.
Corollary 2. Let q be an odd prime power with 3 ∤ q, m and l be two integers. Denote
P1 (x) = xm(q+1)+3q + 3γ l(q−1) xm(q+1)+q+2
and
P2 (x) = 3xm(q+1)+2q+1 + γ l(q−1) xm(q+1)+3 .
Then
1. when l is even, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if gcd(3(2m + 3), q −
1) = 1.
2. when l is odd, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if gcd(2m+3, q−1) = 1
and gcd(3, q + 1) = 1.
Specializing even further to the values m = q − 3, m = 1, or m = 0 yields the following
consequences.

8

Corollary 3. Let q be an odd prime power with 3 ∤ q, and l be an integer. Denote
P1 (x) = xq−2 + 3γ l(q−1) xq
and
P2 (x) = 3xq

2 −2

2 −q−1

+ γ l(q−1) xq

2 −2q

.

Then
1. when l is even, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if q 6≡ 1 (mod 3).
2. when l is odd, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if q 6≡ −1 (mod 3).
Remark 3. Indeed, when m = q − 2, we still have that gcd(2(q − 2)+ 3, q − 1) = gcd(2(q − 1)+ 1, q −
1) = gcd(1, q − 1) = 1. Therefore, substituting m = q − 2 into Corollary 2, we obtain polynomials
P1 (x) = x2q−1 + 3γ l(q−1) x
and
P2 (x) = 3xq + γ l(q−1) xq

2 −q+1

.

The conclusions in Corollary 3 are still valid for the above polynomials P1 and P2 .
Corollary 4. Let q be an odd prime power with 3 ∤ q, and l be an integer. Denote
P1 (x) = x4q+1 + 3γ l(q−1) x2q+3
and
P2 (x) = 3x3q+2 + γ l(q−1) xq+4 .
Then
1. when l is even, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if q 6≡ 1 (mod 3)
and q 6≡ 1 (mod 5).
2. when l is odd, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if q 6≡ −1 (mod 3)
and q 6≡ 1 (mod 5).
Corollary 5. Let q be an odd prime power with 3 ∤ q, and l be an even integer. Then the polynomials
P1 (x) = x3q + 3γ l(q−1) xq+2
and
P2 (x) = 3x2q+1 + γ l(q−1) x3
permute Fq2 if and only if q 6≡ 1 (mod 3).
Continuing using the recursive relations (4) or (5), we have
G5 (x, α) = x5 + 10αx3 + 5α2 x,
and
H5 (x, α) = 5x4 + 10αx2 + α2 .
By Theorem 1 and 2, we obtain the following permutation trinomials over Fq2 .
9

Corollary 6. Let q be an odd prime power with 5 ∤ q, m and l be two integers. Denote
P1 (x) = xm(q+1)+5q + 10γ l(q−1) xm(q+1)+3q+2 + 5γ 2l(q−1) xm(q+1)+q+4
and
P2 (x) = 5xm(q+1)+4q+1 + 10γ l(q−1) xm(q+1)+2q+3 + γ 2l(q−1) xm(q+1)+5 .
Then
1. when l is even, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if gcd(5(2m + 5), q −
1) = 1.
2. when l is odd, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if gcd(2m+5, q−1) = 1
and gcd(5, q + 1) = 1.
Similarly, we specialize further to the values m = q − 4, m = 1, or m = 0 obtain the following
consequences.
Corollary 7. Let q be an odd prime power with 5 ∤ q, and l be an integer. Denote
P1 (x) = x2q−3 + 10γ l(q−1) xq
and
P2 (x) = 5xq−2 + 10γ l(q−1) xq

2 −2

2 −q−1

+ 5γ 2l(q−1) xq
+ γ 2l(q−1) xq

2 −2q

2 −3q+1

.

Then
1. when l is even, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if q 6≡ 1 (mod 5).
2. when l is odd, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if q 6≡ 4 (mod 5).
Remark 4. Similarly, when m = q − 3, we still have that gcd(2(q − 3) + 5, q − 1) = gcd(2(q −
1) + 1, q − 1) = gcd(1, q − 1) = 1. Therefore, substituting m = q − 3 into Corollary 6, we obtain
polynomials
2
P1 (x) = x3q−2 + 10γ l(q−1) xq + 5γ 2l(q−1) xq −q+1
and
P2 (x) = 5x2q−1 + 10γ l(q−1) x + γ 2l(q−1) xq

2 −2q+2

.

The conclusions in Corollary 7 are still valid for the above polynomials P1 and P2 .
Corollary 8. Let q be an odd prime power with 5 ∤ q, and l be an integer. Denote
P1 (x) = x6q+1 + 10γ l(q−1) x4q+3 + 5γ 2l(q−1) x2q+5
and
P2 (x) = 5x5q+2 + 10γ l(q−1) x3q+4 + γ 2l(q−1) xq+6 .
Then
1. when l is even, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if q 6≡ 1 (mod 5)
and q 6≡ 1 (mod 7).
2. when l is odd, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if q 6≡ 4 (mod 5) and
q 6≡ 1 (mod 7).
10

Corollary 9. Let q be an odd prime power with 5 ∤ q, and l be an integer. Denote
P1 (x) = x5q + 10γ l(q−1) x3q+2 + 5γ 2l(q−1) xq+4
and
P2 (x) = 5x4q+1 + 10γ l(q−1) x2q+3 + γ 2l(q−1) x5 .
Then
1. when l is even, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if q 6≡ 1 (mod 5).
2. when l is odd, the polynomials P1 (x) and P2 (x) permute Fq2 if and only if q 6≡ 1, 4 (mod 5).
Similarly as above permutation binomials and trinomilas, in fact, by the relations (4) or (5), we
can generate
recursively permutation polynomials with arbitrary number of terms. For instance, if
n
n+m(q+1) G (xq−1 , α)
p ∤ 2i for 0 ≤ i ≤ n−1
n
2 , then both the two classes of permutation polynomials x
n+1
n+m(q+1)
q−1
and x
Hn (x , α) consist of 2 terms over Fq2 .
4. Compositional Inverse Functions
In this section, we consider the compositional inverses of the two classes of permutation polynomials constructed in last section.
Now we return to the cyclotomic mapping polynomial defined as (1), then the class of permutation polynomials xn+m(q+1) Hn (xq−1 , α) in Theorem 1 can be rewritten as

0,
if x = 0,
P (x) =
Ai xn+m(q+1) , if x ∈ Ci = {γ k(q+1)+i : k = 0, 1, . . . , q − 2}, 0 ≤ i ≤ q,
where Ai = Hn (γ (q−1)i , α). Let γ be a primitive element of Fq2 and ω = γ q−1 . Then, for any x ∈ Ci ,
it is easy to check that
(
l
q 
q
0, if i 6= j,
1 X xq−1
1 X l(i−j)
=
ζ
=
q+1
ζj
q+1
1, if i = j.
l=0
l=0
Then the class of permutation polynomials xn+m(q+1) Hn (xq−1 , α) in Theorem 1 can be uniquely
represented as


q  q−1 j
q
X
x
1 X

Ai xn+m(q+1) 
P (x) =
q+1
ζi
j=0

i=0

=

1
q+1

q
X

Ai ζ −ij xn+m(q+1)+(q−1)j

i,j=0

2

(mod xq − x).

The compositional inverse can then be determined easily by the Theorem 3.3 in [ZYZP16] or Theorem 1 in [Wan17].
P

−1

 ′
q
1 X t1 i−(n+m(q+1))ij x r1 +(q−1)j
ζ
(x) =
q+1
Ai
i,j=0

where r1′ , t1 ∈ Z satisfy (n + m(q + 1))r1′ + (q − 1)t1 = 1.
11

2

(mod xq − x),

(17)

Similarly, we can obtain the compositional inverse of the class of permutation polynomials in
Theorem 2.
 ′
q
1 X t2 i−(n+m(q+1))ij x r2 +(q−1)j
2
−1
(18)
(mod xq − x),
ζ
P (x) =
q+1
Bi
i,j=0

where r2′ , t2 ∈ Z satisfy (n + m(q + 1))r2′ + (q − 1)t2 = 1, and Bi = Gn (γ (q−1)i , α).
From (17) and (18), both the compositional inverses of the two classes of permutation polynomials consist of q + 1 terms, and each of the coefficients is a sum of q + 1 elements. When q is
very large, the computing of their compositional inverses is very inefficient. In the following we
shall give another form of their compositional inverses, which have a relative simpler form. The
following lemma is needed. The original statement is due to Li et al. [LQW17], here we make a
slight modification to apply to our constructions.
Lemma 3. Suppose that P (x) = xr f (xq−1 ) is a permutation polynomial over Fq2 , and gcd(r, q 2 −
1) = 1. Let I(x) be the compositional inverse of the polynomial xr f (x)q−1 over µq+1 , and r ′ be an
integer such that rr ′ ≡ 1 (mod q 2 − 1). Then the compositional inverse of P (x) over Fq2 is equal to
 2

q−2 r′
I xq−1 .
P −1 (x) = xq −q+1 f I xq−1

Proof. It is sufficient to show that for any x ∈ Fq2 , it holds that P −1 (P (x)) = x.
When x = 0, we can easily see that P −1 (0) = 0. Hence, P −1 (P (0)) = P −1 (0) = 0.
When x 6= 0, then P (x) 6= 0. So we can easily obtain P (x)q−1 ∈ µq+1 , and check that



q−1 
r
q−1 
= I xq−1 f xq−1
= xq−1 .
I P (x)q−1 = I xr(q−1) f xq−1
Therefore,

P

−1



 r′
q 2 −q+1
q−1 q−2
I P (x)q−1
(P (x)) = P (x)
f I P (x)

q2 −q+1
q−2 r′ q−1
2
x
= xr(q −q+1) f xq−1
f xq−1
r′ (q2 −1)
2
= xq f xq−1
r′ (q2 −1)
= xf xq−1
.

Note that x 6= 0, then xq−1 ∈ µq+1 . Since P (x) = xr f (xq−1 ) is a permutation polynomial over
 Fq 2 ,
r
q−1
q−1
permutes µq+1 . This implies that f x
6= 0.
then by Corollary 1, we must have that x f (x)
q2 −1
−1
q−1
= 1. Therefore, P (P (x)) = x.
We further obtain that f x
This completes the proof.

Next we computer the compositional inverse function of xn Hn (x, α)q−1 over µq+1 . For the sake
of convenience, let r ′ be an integer such that (n + m(q + 1))r ′ ≡ 1 (mod q 2 − 1). Then by equations
(9), (6) and (7), we have
√
√
1
((x + α)n + (x − α)n )
n−1
Gn (x, α)
n
q−1
− n−1
−
2
x Hn (x, α)
=α 2
=α 2 1
√
√
√ ((x + α)n − (x − α)n )
Hn (x, α)
2 α
(19)
√ n
√ n
n
(x
+
α)
+
(x
−
α)
√
√
= α− 2 +1
.
(x + α)n − (x − α)n
√
Below we distinguish two cases according to whether α ∈ µq+1 or not.
12

1.

√

α ∈ µq+1 . First we need to verify the hypotheses of Lemma 3, namely that gcd(n + m(q +
1), q 2 − 1) = 1. This is equivalent to gcd(n + m(q + 1), q − 1) = gcd(n + 2m, q − 1) = 1
and gcd(n + m(q + 1), q + 1) = gcd(n, q + 1) = 1. Therefore, we additionally suppose that
gcd(n, q + 1) = 1.
√
√
√
n
If x = α, then by equation (19), we have ( α)n Hn ( α, α)q−1 = α− 2 +1 . So the preimage
√
√
n
n
of α− 2 +1 is equal to α. Similarly, the preimage of −α− 2 +1 is equal to − α.
√
If x 6= ± α, then we have
 √ n
x+√α
+1
n
q−1
−n
+1  x− α 
2
= l2 (x) ◦ xn ◦ l1 (x),
x Hn (x, α)
=α
√
n
x+√α
−1
x− α

√
n
x+ α
x+1
√ , l2 (x) = α− 2 +1
are linear fractional transformations. From
x−1
x− α
equation (14), we know that l1 (x) ∈ µ2(q−1) . Note that gcd(n, 2(q − 1)) = gcd(n, q − 1) = 1,
then xn permutes µ2(q−1) . Hence we can easily obtain the compositional inverse I1 (x) of
√
√
n
n
function xn Hn (x, α)q−1 : µq+1 \ { α, − α} → µq+1 \ {α− 2 +1 , −α− 2 +1 },
 n
 n1  n
 n1
−1
−1
2
2
α
x+1
x−1
+ α
√
 n1  n
 n1 ,
I1 (x) = l1−1 (x) ◦ xn1 ◦ l2−1 (x) = α ·  n
− α 2 −1 x − 1
α 2 −1 x + 1
where l1 (x) =

where n1 is an integer such that nn1 ≡ 1 (mod 2(q − 1)).

√
√
n
n
Then, a straightforward calculation yields that I1 (α− 2 +1 ) = α, I1 (−α− 2 +1 ) = − α.
This implies that the compositional inverse of xn Hn (x, α)q−1 over µq+1 is equal to I1 (x). By
Lemma 3, the compositional inverse of P (x) = xn+m(q+1) Hn (xq−1 , α) over Fq2 is equal to
′

P −1 (x) = xr (q
2.

2 −q+1)

√

r′ (q−2)
I1 (xq−1 ).
Hn I1 (xq−1 ), α

α∈
/ µq+1 . From gcd(n + 2m, q − 1) = gcd(n + m(q + 1), q − 1) = 1 and gcd(n, q + 1) =
gcd(n + m(q + 1), q + 1) = 1, we can obtain gcd(n + m(q + 1), q 2 − 1) = 1. Noticed that
√
± α∈
/ µq+1 , then almost identically to case 1, we can obtain the compositional inverse of
n
x Hn (x, α)q−1 over µq+1 is equal to
 n
 n2  n
 n2
−1
−1
2
2
α
x
+
1
x
−
1
+
α
√
 n2  n
 n2 ,
I2 (x) = l1−1 (x) ◦ xn2 ◦ l2−1 (x) = α ·  n
− α 2 −1 x − 1
α 2 −1 x + 1
where n2 is an integer such that nn2 ≡ 1 (mod 2(q + 1)). In this case the compositional
inverse of P (x) = xn+m(q+1) Hn (xq−1 , α) is equal to
′

P −1 (x) = xr (q

2 −q+1)

r′ (q−2)
I2 (xq−1 ).
Hn I2 (xq−1 ), α

We know that every permutation on Fq2 can be expressed as a permutation polynomial over
Fq2 . Indeed we can express the compositional inverse permutation P −1 (x) as a polynomial over Fq2 .

13

Now let’s look at the function I1 (x). By (19), we have that
 n
 n1  n
 n1
−1
−1
2
2
α
x
+
1
x
−
1
+
α
√
 n1  n
 n1
I1 (x) = α ·  n
α 2 −1 x + 1
− α 2 −1 x − 1
 n−1
√ n1  n−1
√  n1
2 x +
2 x −
α
α
α
+
α
√


= α ·  n−1
n
1
√
√  n1
n−1
α 2 x+ α
− α 2 x− α
 n−1 n1
 n−1
q−1
n1
1
= α 2 α 2 −1 α 2 x
Hn1 α 2 x, α
 n−1
q−1
nn1 −1
.
= α 2 xn1 Hn1 α 2 x, α
For the function I2 (x), note that nn2 ≡ 1 (mod 2(q + 1)), then we have α

nn2 −1
2

= 1. Therefore,

q−1
 n−1
2
x, α
.
I2 (x) = x Hn2 α
n2

We summarize the preceding discussion as the following theorems.
Theorem 3. Suppose n > 0 and m are two integers. Let α ∈ Fq2 satisfy αq+1 = 1, and r ′ be an
integer such that (n + m(q + 1)) r ′ ≡ 1 (mod q 2 − 1). Define polynomial
P (x) = xn+m(q+1) Hn (xq−1 , α).
Then the following statements hold.
√
1. When α ∈ µq+1 , gcd(n(n + 2m), q − 1) = 1 and gcd(n, q + 1) = 1, the compositional inverse
function of P (x) over Fq2 is equal to
′

P −1 (x) = xr (q

2 −q+1)

where
I1 (x) = α

nn1 −1
2

r′ (q−2)
Hn I1 (xq−1 ), α
I1 (xq−1 ),

 n
 n1  n
 n1
 n−1
q−1 √
α 2 −1 x + 1
+ α 2 −1 x − 1
 n1  n
 n1 ,
xn1 Hn1 α 2 x, α
= α·  n
−1
−1
2
2
α
x+1
x−1
− α

and n1 is an integer such that nn1 ≡ 1 (mod 2(q − 1)).
√
2. When α ∈
/ µq+1 , gcd(n + 2m, q − 1) = 1 and gcd(n, q + 1) = 1, the compositional inverse
function of P (x) over Fq2 is equal to
′

P −1 (x) = xr (q
where

2 −q+1)

r′ (q−2)
Hn I2 (xq−1 ), α
I2 (xq−1 ),

 n
 n2  n
 n2
q−1 √
 n−1
α 2 −1 x + 1
+ α 2 −1 x − 1
 n2  n
 n2 ,
= α·  n
I2 (x) = xn2 Hn2 α 2 x, α
− α 2 −1 x − 1
α 2 −1 x + 1

and n2 is an integer such that nn2 ≡ 1 (mod 2(q + 1)).
14

Similarly, we can also obtain the compositional inverses of permutation polynomials constructed
in Theorem 2.
Theorem 4. Suppose n > 0 and m are two integers. Let α ∈ Fq2 satisfy αq+1 = 1, and r ′ be an
integer such that (n + m(q + 1)) r ′ ≡ 1 (mod q 2 − 1). Define polynomial
P (x) = xn+m(q+1) Gn (xq−1 , α).
Then the following statements hold.
√
1. When α ∈ µq+1 , gcd(n(n + 2m), q − 1) = 1 and gcd(n, q + 1) = 1, the compositional inverse
function of P (x) over Fq2 is equal to
′

P −1 (x) = xr (q

2 −q+1)

where

r′ (q−2)
I3 (xq−1 ),
Gn I3 (xq−1 ), α

 n1  n
n1
 n
2x + 1
2x − 1


−
α
α
q−1
nn1 +1
√
n+1
 n1  n
n1 ,
= α·  n
I3 (x) = αn1 + 2 xn1 Gn1 α 2 x, α
α2 x + 1
+ α2 x − 1

and n1 is an integer such that nn1 ≡ 1 (mod 2(q − 1)).
√
/ µq+1 , gcd(n + 2m, q − 1) = 1 and gcd(n, q + 1) = 1, the compositional inverse
2. When α ∈
function of P (x) over Fq2 is equal to
′

P −1 (x) = xr (q
where
I4 (x) = αn2 +1 xn2 Gn2



2 −q+1)

r′ (q−2)
I4 (xq−1 ),
Gn I4 (xq−1 ), α

 n
 n2  n
 n2
2x +1
2x − 1

α
−
α
q−1
√
n+1
 n2  n
 n2 ,
α 2 x, α
= α·  n
α2x +1
+ α2x − 1

and n2 is an integer such that nn2 ≡ 1 (mod 2(q + 1)).
Acknowledgments

This work was supported by the National Key Research and Development Program of China
(No. 2016YFB0800401), the National Natural Science Foundation of China (No. 61572491 and
11688101) and NSERC of Canada.
References
[AGW11] Amir Akbary, Dragos Ghioca, and Qiang Wang. On constructing permutations of finite fields. Finite
Fields and Their Applications, 17(1):51–67, 2011.
[CDY05] Claude Carlet, Cunsheng Ding, and Jin Yuan. Linear codes from perfect nonlinear mappings and their
secret sharing schemes. IEEE Transactions on Information Theory, 51(6):2089–2102, 2005.
[DH13] Cunsheng Ding and Tor Helleseth. Optimal ternary cyclic codes from monomials. IEEE Transactions on
Information Theory, 59(9):5898–5904, 2013.

15

[DY06] Cunsheng Ding and Jin Yuan. A family of skew hadamard difference sets. Journal of Combinatorial
Theory, Series A, 113(7):1526–1535, 2006.
[DY07] Cunsheng Ding and Jianxing Yin. Signal sets from functions with optimum nonlinearity. IEEE Transactions on Communications, 55(5):936–940, 2007.
[HMSY09] Xiang-dong Hou, Gary L. Mullen, James A. Sellers, and Joseph L. Yucas. Reversed dickson polynomials
over finite fields. Finite Fields and Their Applications, 15(6):748–773, 2009.
[Hou15] Xiang-dong Hou. Permutation polynomials over finite fields - A survey of recent advances. Finite Fields
and Their Applications, 32:82–119, 2015.
[Lai07] Yann Laigle-Chapuy. Permutation polynomials and applications to coding theory. Finite Fields and Their
Applications, 13(1):58–70, 2007.
[LM83] Rudolf Lidl and Winfried B. Müller. Permutation polynomials in RSA-cryptosystems. In Advances in
Cryptology, Proceedings of CRYPTO’83, Santa Barbara, California, USA, August 21-24, 1983., pages
293–301, 1983.
[LMT93] Rudolf Lidl, Gary L Mullen, and Gerhard Turnwald. Dickson polynomials, volume 65 of Monographs and
Surveys in Pure and Applied Mathematics. Chapman and Hall/CRC, 1993.
[LN97] Rudolf Lidl and Harald Niederreiter. Finite fields, volume 20 of Encyclopedia of Mathematica and its
Applications. Cambridge University Press, 2nd edition, 1997.
[LP97] June Lee and Young Ho Park. Some permuting trinomials over finite fields. Acta Mathematica Scientia.
Series B. (English Edition), 17:250–254, 07 1997.
[LQW17] Kangquan Li, Longjiang Qu, and Qiang Wang. Compositional inverses of permutation polynomials of the
form xr h(xs ) over finite fields. Preprint, 2017.
[MP13] Gary L Mullen and Daniel Panario. Handbook of finite fields. CRC Press, 2013.
[NW05] Harald Niederreiter and Arne Winterhof. Cyclotomic R-orthomorphisms of finite fields. Discrete Mathematics, 295(1-3):161–171, 2005.
[RSA78] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and
public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978.
[SH98] Jörg Schwenk and Klaus Huber. Public key encryption and digital signatures based on permutation
polynomials. Electronics Letters, 34(8):759–760, 1998.
[Wan07] Qiang Wang. Cyclotomic mapping permutation polynomials over finite fields. In Sequences, Subsequences,
and Consequences, International Workshop, SSC 2007, Los Angeles, CA, USA, May 31 - June 2, 2007,
Revised Invited Papers, pages 119–128, 2007.
[Wan17] Qiang Wang. A note on inverses of cyclotomic mapping permutation polynomials over finite fields. Finite
Fields and Their Applications, 45:422–427, 2017.
[YCD06] Jin Yuan, Claude Carlet, and Cunsheng Ding. The weight distribution of a class of linear codes from
perfect nonlinear functions. IEEE Transactions on Information Theory, 52(2):712–717, 2006.
[YD11] Pingzhi Yuan and Cunsheng Ding. Permutation polynomials over finite fields from a powerful lemma.
Finite Fields and Their Applications, 17(6):560–574, 2011.
[YD14] Pingzhi Yuan and Cunsheng Ding. Further results on permutation polynomials over finite fields. Finite
Fields and Their Applications, 27:88–103, 2014.
[Zie09] Michael E. Zieve. On some permutation polynomials over Fq of the form xr h(x(q−1)/d ). Proceedings of
the American Mathematical Society, 137(7):2209–2216, 2009.
[Zie13] Michael Zieve. Permutation polynomials on Fq induced from bijective Rédei functions on subgroups of
the multiplicative group of F∗q . arXiv, abs/1310.0776, 2013.
[ZYZP16] Yanbin Zheng, Yuyin Yu, Yuanping Zhang, and Dingyi Pei. Piecewise constructions of inverses of cyclotomic mapping permutation polynomials. Finite Fields and Their Applications, 40:1–9, 2016.

16

