Journal of Computer and Communications, 2014, 2, 18-24
Published Online March 2014 in SciRes. http://www.scirp.org/journal/jcc
http://dx.doi.org/10.4236/jcc.2014.24003
How to cite this paper: Sun, G.H. (2014) Several Classes of Permutation Polynomials over Finite Fields. Journal of Computer
and Communications, 2, 18-24. http://dx.doi.org/10.4236/jcc.2014.24003
Several Classes of Permutation Polynomials
over Finite Fields
Guanghong Sun
College of Sciences, Hohai University, Nanjing, China
Received October 2013
Abstract
Several classes of permutation polynomials of the form
() ()
k
pt
x x+δ+L x−
over finite fields are
presented in this paper, which is a further investigation on a recent work of Li et al.
Keywords
Permutation Polynomial; Finite Fields
1. Introduction
Let
p
be a prime and
n
p
F
denote a finite field with
n
p
elements. A polynomial
() []
n
p
fxF x∈
is called a
permutation polynomial over
n
p
F
if it induces a one-to-one map from
n
p
F
to itself. Permutation polynomials
were first studied by Hermite [1] for the case of finite prime fields and by Dickson [4] for arbitrary finite fields.
Permutation polynomials have been studied extensively and have important applications in coding theory, cryp-
tography, combinatorics, and design theory [3-6]. In the recent years, there has been significant progress in find-
ing new permutation polynomials [7-12].
The determination of permutation polynomials is not an easy problem. An important class of permutation po-
lynomials is of the form
()( ),
k
pt
x xLx δ −+ +
(1)
where
,kt
are integers,
n
p
F δ ∈
and
()Lx
is a linearized polynomial. In [13], Helleseth and Zinoviev de-
rived new identities on Kloosterman sums by making use of this kind of permutation polynomials. Followed by
the research of Helleseth and Zinoviev, many researchers began to study such class of permutation polynomials
and numerical results were obtained [14-18].
In this paper, inspired by permutation polynomials obtained by Zha and Hu in [18]} and Li et al. in [19 ], we
investigate several new classes of permutation polynomials of the form (1) with
1
2
nr
p
tp
−
= +
, where
p
is
an odd prime and
r
is a nonnegative integer.
This paper is organized as follows. In Section 2, we present several classes of permutation polynomials over
3n
F
, which are not covered by [18,19], and over
n
p
F
. We conclude the paper in Section 3.

G. H. Sun
19
2. Permutation Polynomials over
3n
F
In this section, we study the permutation polynomials of the form (1) with
1
2
nr
p
tp
−
= +
over
3
n
F
. Th ese
permutation polynomials are not covered by [18,19].
The trace function from
n
p
F
to its subfield
k
p
F
, where
|kn
, is defined by
2
() k knk
npp p
k
Trxxxxx − =+ +++
.
Let
α
be a primitive element of
n
p
F
, define
2
0
D α =<>
, and
10
DD α =
. Then
01
{0}
n
p
F DD= ∪∪
. Ob-
viously, when
i
xD∈
, we have that
1( 1)
22
( 1)
nn
ppi i
x α
−−
== −
for
0,1i=
.
When
0,1i=
, Li et al. in [19] investigates the permutatio n polynomials with the form of
31
3
33
2
()
nik
kk
xx xx δ
−+
−++ +
.
The following theorem shows that it is also a permutation polynomial when
2i=
.
Theorem 1 Let
3nk =
, where
k
is a positive integer, and
3
n
F
δ ∈
with
()0
n
k
Tr δ =
. Then
2
31
3
33
2
()
nk
kk
xx xx δ
−+
−++ +
is a permutation polynomial over
3
n
F
.
Proof For any
3
n
bF∈
, it is sufficient to prove the
Equation
2
31
3
33
2
()
nk
kk
x xx xb δ
−+
−++ +=
(2)
has exactly one solution over
3
n
F
.
If
x
is a solution of the Equation (2), then we consider three cases in the following.
1) Case A:
3
0
k
xx δ −+ =
. By (2), we have
3
k
x xb+=
. Then the two Equations lead to
xb δ =−−
. Hence
3 33
k kk
xx bb δ δδ −+ =−+−−
.
2) Case B:
30
k
xx D δ −+∈
. By (2), we have
22
33 3
kk k
xxxb δ −+ −=−
. (3)
Raising the
3
k
th power on the both sides of Equation (3), we have
2
3 33
.
kk k
xxx b δ −+−= −
( 4)
By Equations (3) and (4), we have
2
33
kk
xbb δδ =+−−
. Hence
22
33 33
.
kk kk
xxbb δδ δδ −+ =−+−+
By
()0
n
k
Tr δ =
,
2
3 33
.
k kk
xxbb δδ −+ =−+
3) Case C:
31
k
xxD δ −+∈
. By (2), we have
22
33 3
kk k
x xb
δ +=+
. Raising the
3
k
th and
2
3k
th power on
the both sides of the above Equation, respectively, we have
2
33
kk
xx b δ +=+
and
2
3 33
k kk
x xb δ += +
. By the
three Equations, we have
22
333 3
kkk k
xbb b δδ δ
=−−−−+
. So
2
3 33
k kk
x xbb δδ −+ =+−
.
Let
2
33
kk
bb δ = +−
, then
2
33
kk
xx δ −+ =
in Case B.
If Case A happens, namely,
33
0
kk
bb δδ −+−− =
, then
22
3 3 33
0
k kkk
bb δδδ δ =+−= ++=
. Hence only
one case will happen in the above three cases. So
2
31
3
33
2
()
nk
kk
x xx xb δ
−+
−++ +=
has exactly one solution
over
3
k
F
, that is to say,
2
31
3
33
2
()
nk
kk
xx xx δ
−+
−++ +
is a permutation polynomial over
3
n
F
. The theorem
holds.

G. H. Sun
20
The following theorems give several new classes of permutation polynomials which are not covered by
[18,19].
Theorem 2 Let
3nk=
, where
k
is a positive integer, and
3
n
F δ ∈
with
()0
n
k
Tr δ =
. Then
2
31
3
33
2
()
nik
kk
xxx x δ
−+
−++ +
is a permutation polynomial over
3
n
F
for any
0,1i=
or 2.
Proof For all
3
n
bF ∈
, it is sufficient to prove the Equation
2
31
3
33
2
()
nik
kk
x xxxb δ
−+
−++ +=
has exactly one
solution over
3
n
F
for any
0,1i=
or 2. For
0,1i=
or 2, the proof is similar, so we only prove the permuta-
tion polynomial for
1i=
, namely,
2
31
3
33
2
()
nk
kk
x xxxb δ
−+
−+++=
(5)
If
x
is a solution of the Equation (5), then we consider three cases in the following.
1) Case A:
3
0
k
xx δ −+ =
. By (5), we have
2
3
k
x xb+=
. Raising the
3
k
th power on both sides, we have
33
kk
xxb +=
. By
30
k
xx δ −+ =
and
33
kk
xx b+=
, we have
3
k
xb δ =−−
. Hence
2
33 33
kkk k
xxb b δ δδ −+ =−+−−
.
2) Case B:
30
k
xx D δ −+∈
. By (5), we have
2
33 3
kk k
xxxb δ −− +=−
. Raising the
3
k
th power and
2
3k
th
power on the both sides of the above Equation, respectively, then we have
22
3 333
kkk k
xxxb
δ −−+= −
and
22
3 33
k kk
x xxb
δ − −+=−
. By the two Equations, we have
22
333
kkk
xb b δδ =−+−
. Hence
3 33
k kk
x xbb
δδ −+ =−+
.
3) Case C:
31
k
xxD δ −+∈
. By (5), we have
33
kk
x xb δ +=+
. Raising the
3
k
th power and
2
3k
th
power on the both sides of the above Equation, respectively, then we have
22
3 333
kkk k
x xb δ +=+
and
22
33
kk
xx b δ +=+
.
By the three equations, we have
22
3333
()( )
k kkk
xbbb δδ δ =−+ −+++
. Henc e
22
33 33
kkk k
xxb b δδ
−+ =−++
.
Let
33
kk
bb δ =−+
. Then
22
333 3
kk kk
bb δ − ++=
in Case C.
If Case A occurs, namely,
2
3 33
0
kk k
bb δδ −+−−=
, then we have
2
33
0
kk
δδ δ =++=
. Hence only one
case will happen in the above three cases. Therefore,
2
31
3
33
2
()
nk
kk
x xxxb δ
−+
−++ +=
has exactly one solution
over
3
n
F
, that is to say,
2
31
3
33
2
()
nk
kk
xxx x δ
−+
−++ +
is a permutation polynomial over
3
n
F
. The theorem holds.
Theorem 3 Let
3 nk=
, where
k
is a positive integer, and
3
n
F δ ∈
with
()0
n
k
Tr δ =
. Then
2
31
3
3 33
2
()
nik
k kk
xxx xx δ
−+
−+++−
is a permutation polynomial over
3
n
F
for any
0,1i=
or
2
.
Proof Since the proof is similar for any
0,1i=
or 2, we only prove the permutation polynomial when
1 i=
.
For all
3
k
bF∈
, it is sufficient to prove
2
31
3
3 33
2
()
nk
k kk
xxx xxb δ
−+
−+++ −=
(6)
has exactly one solution over
3
k
F
. If
x
is a solution of the Equation (6), then we consider three cases in the
following.
1) Case A:
3
0
k
xx δ −+ =
. By (6), we have
2
33
kk
xxxb+ −=
.
By the two Equations, we have
2
3
k
xb δ = +
.
So
33
kk
xb δ = +
and
22
333 33
kkkk k
xx bb δ δδδ −+ =+−−+
.
2) Case B:
30
k
xxD δ −+∈
. By (6), we have
2
33
kk
xx b δ += −
. Let
3
k
ub δ = −
, then
33
kk
xx u+=
and
22
33 3
kk k
xx u+=
. By the three Equations, we have
2
33
kk
xuuu= −−
. So
2
3 33
k kk
xxb b δ δδ −+ =−+−−
.
3) Case C:
31
k
xx D δ −+∈
. By (6), we have
33
kk
xxb δ + =−−
. Let
3
k
vb δ =−−
, then
2
3 33
kkk
x xv+=
and
22
33
kk
xx v+=
. By the three Equations, we have
2
33
kk
xv vv=− +−
. Hence

G. H. Sun
21
22
33 33
kkk k
xxb b δ δδ −+ =−−−
.
Let
2
33
kk
bb δδ =− +− −
, then
2 22
3 333
kk kk
bb δδ − −−=
in Case C.
If Case A occurs, then we have
2
33
( )0
kk
δδ δ =−+ +=
. Hence only one case will happen in the above three
cases. Therefore,
2
31
3
3 33
2
()
nk
k kk
xxx xxb δ
−+
−+++ −=
has exactly one solution over
3
n
F
. The theorem holds.
In the above section, we consider permutation polynomials over
3
n
F
. In the following, we investigate permu-
tation polynomials over
n
p
F
for an odd prime
p
.
Theorem 4 Let
4nk=
, where
k
is a positive integer and
p
be an odd prime. Then
22
1
2
()
nik
kk
pp
pp
xx xx δ
−+
−+++
is a permutation polynomial over
n
p
F
for any
0,1, 2i=
or
3
.
Proof For all
n
p
bF∈
, it is sufficient to prove
22
1
2
()
nik
kk
pp
pp
x xx xb δ
−+
−+++=
only have a solution over
n
p
F
for any
0,1, 2i=
or 3.
Since the proof is similar for
0i=
or 2, we only consider
0i=
.
Similarly, the proof is also similar for
1i=
or 3, so we only consid er
1i=
.
For
0i=
, if
x
is a solution of the equatio n
22
11
2
()
n
kk
p
pp
x xx xb δ
−+
−+++=
, then we consider three cases
in the following.
1) Case A
0
:
20 k
p
xx δ −+ =
. Then we have
2k
p
x xb+=
. Hence
1()
2
xb δ = +
. Therefore,
2 22
1()
2
k kk
p pp
xxbb δ δδ −+ =−++
.
2) Case B
0
:
2
0
k
p
xx D δ −+∈
. Then we have
2
1()
2
k
p
xb δ = −
and
22
1()
2
kk
pp
xb δ = −
. Hence
2 22
1()
2
k kk
p pp
x xbb δ δδ −+ =−++
.
3) Case C
0
:
2
1
k
p
xxD δ −+∈
. Then we have
1()
2
xb δ = +
. Hence
2 22
1()
2
k kk
p pp
xxbb δ δδ −+ =−++
.
Hence only one case will occur in the above three cases. Therefore,
22
11
2
()
n
kk
p
pp
x xx xb δ
−+
−+++=
only
have a solution over
n
p
F
.
For
1i=
, if
x
is a solution of the equation
22
1
2
()
nk
kk
pp
pp
x xx xb δ
−+
−+++=
,
then we also consider three cases in the following.
1) Case A
1
:
2
0
k
p
xx δ −+ =
. Then we have
2k
p
x xb+=
. Hence
1()
2
xb δ = +
. Therefore,
2 22
1()
2
k kk
p pp
xxbb δ δδ −+ =−++
.
2) Case B
1
:
2
0
k
p
xxD δ −+∈
. Then we have
32
.
k kkk
ppp p
xxxxb δ +− +=−
(7)
Let
k
p
ub δ = −
. Then raising the
k
p
th power,
2k
p
th power, and
3k
p
th power on the both sides for Equa-
tion (7), respectively, we have
32 kkkk
p p pp
xxxxu+ − +=
(8)
32 2kkk k
ppp p
x xxxu+− +=
(9)

G. H. Sun
22
2 33kkk k
pp pp
xxxxu+ −+=
(10)
Adding (7) to (8), we have
3
22 .
kk
pp
x xuu+=+
(11)
Subtracting (10) from (9), we have
3 23
22 .
k kk
ppp
xxu u−=−
(12 )
Adding (11) to (12), we have
23
4
kkk
pp p
xuu uu =++ −
.
Hence
23
1()
4
kkk
pp p
xuu uu= ++−
and
2 32
1()
2
kkk k
pppp
xx bb δ δδ −+ =−++
.
3) Case C
1
:
2
1
k
p
xxD δ −+∈
. Then we have
32
.
k kkk
ppp p
xxxxb δ −−− =−−
(13)
Let
k
p
vb δ =−−
. Raising the
k
p
th power, 2k
pth power, and 3k pth power on the both sides of Equation
(13), respectively, then we obtain
32k kkk
p p pp
xxxx v− − −=
(14)
322k kkk
p ppp
x xxxv−− −=
(15)
2 33 kkk k
pp pp
xxxxv− −−=
( 16)
Subtracting (13) from (14), then we obtain
3
22 .
kk
pp
xxv v−=−
(17)
Adding (15) to (16), then we have
3 23
22 .
k kk
ppp
xxv v−−= +
(18)
Subtracting (18) from (17), then we obtain
23
4kkk
pp p
x vvvv=−+ −−
.
Hence
23
1()
4
kkk
pp p
xvvvv= −+−−
and
2 32
1()
2
kkk k
pp pp
xx bb δ δδ −+ =−+++
.
Let
32 kk k
p pp
bb δδ = −++
. Then
3 22kk kk
p ppp
bb δδ −+ ++=
in the Case C
1
.
If Case A
1
occurs, then
22
0
kk
pp
bb δδ −++ =
.
Hence
3232
3223 2222
()()( 0 )
kk kkk k
kkkk kkkk kk
p ppp pp
pp pppppppp
bb bb
xxxx xxxx
δδ δδ
δ δδδ
= −++=−++
=−−++ =− −−−+−+−=


G. H. Sun
23
Hence only one case will occur in the above three cases. Therefore,
22
1
2
()
nk
kk
pp
pp
x xx xb δ
−+
−+++=
only
has a solution over
n
p
F
. The theorem holds.
3. Conclusion
In the paper, we obtain some permutation polynomials of the form
() ()
k
pt
x xLx δ −+ +
with
1
2
nr
p
tp
−
= +
,
which are not covered by [18,19]. It is possible that they have some applications in coding theory, cryptography,
combinatorics, design theory and so on.
Acknowledgements
This work was supported by the Natural Science Foundation of China under Grant No. 61103184, No. 61173134,
and No. 61272542.
References
[1] Hermite, Ch. (1863) Sur les Fonctions de Sept Lettres. C.R. Acad. Sci. Paris, 57, 750-757.
[2] Dickson, L.E. (1896) The Analytic Representation of Substitutions on a power of a Prime Number of Letters with a
Discussion of the Linear Group. Annals of Mathematics, 11, 65-120. http://dx.doi.org/10.2307/1967217
[3] Cohen, S.D. (1997) Permutation Group Theory and Permutation Polyn omials. In: Algebra and Combinatorics,
ICAC’97, Hong Kong, August 1997, 133-146.
[4] Laigle-Chapuy, Y. (2007) Permutation Polynomials and Applications to Coding Theory. Finite Fields and Their Ap-
plications, 13, 58-70. http://dx.doi.org/10.1016/j.ffa.2005.08.003
[5] Lidl, R. and Niederreiter, H. (1997) Finite fields. 2nd Edition, Cambridge University Press.
[6] Mullen, G.L. (1993) Permutation Polynomials over Finite Fi elds. Proceedings of Conference on Finite Fields and
Their Applications, Lecture Notes in Pure and Applied Mathematics, Vol. 141, Marcel Dekker, New York, 131-151.
[7] Cao, X. and Hu, L. (2011) New Methods for Generating Permutation Polynomials over Finite Fields. Finite Fields and
Their Applications, 17, 493-503. http://dx.doi.org/10.1016/j.ffa.2011.02.012
[8] Charpin, P. and Kyureghyan, G. (2009) When Does
() (()) G XTr HX γ +
Permute
()
n
GF p
. Finite Fields and Their
Applications, 15, 615-632. http://dx.doi.org/10.1016/j.ffa.2009.07.001
[9] Ding, C., Xiang, Q., Yua n, J. and Yuan, P. (2009) Explicit Classes of Permutation Polynomials of
3
3
m
F
. Science in
China Series A: Mathematics, 53, 639-647. http://dx.doi.org/10.1007/s11425-008-0142-8
[10] Fernando, N. , Hou, X. and Lappano, S. (2013) A New Approach to Permutation Polynomials over Finite Fields II. Fi-
nite Fields and Their Applications, 18, 492-521. http://dx.doi.org/10.1016/j.ffa.2013.01.001
[11] Hollmann, H.D.L. and Xian g, Q. (2005) A Class of Permutation Polynomials of
2m
F
Related to Dickson Polynomial s.
Finite Fields and Their Applications, 11, 111-122. http://dx.doi.org/10.1016/j.ffa.2004.06.005
[12] Hou, X. (2012) A New Approach to Permutation Polynomials over Finite Fiel ds. Finite Fields and Their Applications,
18, 492-521. http://dx.doi.org/10.1016/j.ffa.2011.11.002
[13] Helleseth, T. and Zinoviev, V. (2003) New Kloosterman Sums Identities over
2m
F
for All
m
. Finite Fields and
Their Applications, 9, 187-193. http://dx.doi.org/10.1016/S1071-5797(02)00028-X
[14] Yuan, J. and Ding, C. (2007) Four Classes of Permutation Polynomials of
2m
F
. Finite Fields and Their Applications,
13, 869-876. http://dx.doi.org/10.1016/j.ffa.2006.05.006
[15] Yuan, J., Ding, C., Wang, H. and Pieprzyk, J. (2008) Permutation Polynomials of the Form
()()
ps
x xLx δ −+ +
. Fi-
nite Fields and Their Applications, 14, 482-493. http://dx.doi.org/10.1016/j.ffa.2007.05.003
[16] Yuan, P. and Ding, C. (2011) Permutation Polynomials over Finite Fields from a Powerful Le mma. Finite Fields and
Their Applications, 17, 560-574. http://dx.doi.org/10.1016/j.ffa.2011.04.001
[17] Zeng, X., Zhu, X. and Hu, L. (2010) Two New Permutation Polynomials with the Form
2
()
ks
xx x δ ++ +
over
2
n
F
.
Applicable Algebra in Engineering, Communication and Computing, 21, 145-150.

G. H. Sun
24
[18] Zha, Z. and Hu, L. (2012) Two Classes of Permutation Polynomials over Finite Fields. Finite Fields and Their Appli-
cations, 18, 781-790. http://dx.doi.org/10.1016/j.ffa.2012.02.003
[19] Li, N., Helleseth, T. and Tang, X. (2013) Further Results on a Class of Permutation Polynomials over Finite Fields. Fi -
nite Fields and Their Applications, 22, 16-23.