Journal of Computer and Communications, 2014, 2, 1824 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, 1824. 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 Email: sgh1976@gmail.co m Received October 2013 Abstract Several classes of permutation polynomials of the form 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 be a prime and denote a finite field with elements. A polynomial is called a permutation polynomial over if it induces a onetoone map from 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 [36]. In the recent years, there has been significant progress in find ing new permutation polynomials [712]. The determination of permutation polynomials is not an easy problem. An important class of permutation po lynomials is of the form (1) where are integers, and 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 [1418]. 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 , where is an odd prime and is a nonnegative integer. This paper is organized as follows. In Section 2, we present several classes of permutation polynomials over , which are not covered by [18,19], and over . We conclude the paper in Section 3.
G. H. Sun 2. Permutation Polynomials over In this section, we study the permutation polynomials of the form (1) with over . Th ese permutation polynomials are not covered by [18,19]. The trace function from to its subfield , where , is defined by 2 () k knk npp p k Trxxxxx − =+ +++ . Let be a primitive element of , define , and . Then . Ob viously, when , we have that 1( 1) 22 ( 1) nn ppi i x α −− == − for . When , 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 . Theorem 1 Let , where is a positive integer, and with . Then 2 31 3 33 2 () nk kk xx xx δ −+ −++ + is a permutation polynomial over . Proof For any , it is sufficient to prove the Equation 2 31 3 33 2 () nk kk x xx xb δ −+ −++ += (2) has exactly one solution over . If is a solution of the Equation (2), then we consider three cases in the following. 1) Case A: . By (2), we have . Then the two Equations lead to . Hence 3 33 k kk xx bb δ δδ −+ =−+−− . 2) Case B: . By (2), we have . (3) Raising the th power on the both sides of Equation (3), we have ( 4) By Equations (3) and (4), we have . Hence 22 33 33 . kk kk xxbb δδ δδ −+ =−+−+ By , 3) Case C: . By (2), we have . Raising the th and th power on the both sides of the above Equation, respectively, we have and . By the three Equations, we have 22 333 3 kkk k xbb b δδ δ =−−−−+ . So . Let , then in Case B. If Case A happens, namely, , 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 , that is to say, 2 31 3 33 2 () nk kk xx xx δ −+ −++ + is a permutation polynomial over . The theorem holds.
G. H. Sun The following theorems give several new classes of permutation polynomials which are not covered by [18,19]. Theorem 2 Let , where is a positive integer, and with . Then 2 31 3 33 2 () nik kk xxx x δ −+ −++ + is a permutation polynomial over for any or 2. Proof For all , it is sufficient to prove the Equation 2 31 3 33 2 () nik kk x xxxb δ −+ −++ += has exactly one solution over for any or 2. For or 2, the proof is similar, so we only prove the permuta tion polynomial for , namely, 2 31 3 33 2 () nk kk x xxxb δ −+ −+++= (5) If is a solution of the Equation (5), then we consider three cases in the following. 1) Case A: . By (5), we have . Raising the th power on both sides, we have . By and , we have . Hence 2 33 33 kkk k xxb b δ δδ −+ =−+−− . 2) Case B: . By (5), we have . Raising the th power and th power on the both sides of the above Equation, respectively, then we have and . By the two Equations, we have . Hence . 3) Case C: . By (5), we have . Raising the th power and th power on the both sides of the above Equation, respectively, then we have and . By the three equations, we have 22 3333 ()( ) k kkk xbbb δδ δ =−+ −+++ . Henc e 22 33 33 kkk k xxb b δδ −+ =−++ . Let . Then in Case C. If Case A occurs, namely, , then we have . 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 , that is to say, 2 31 3 33 2 () nk kk xxx x δ −+ −++ + is a permutation polynomial over . The theorem holds. Theorem 3 Let , where is a positive integer, and with . Then 2 31 3 3 33 2 () nik k kk xxx xx δ −+ −+++− is a permutation polynomial over for any or . Proof Since the proof is similar for any or 2, we only prove the permutation polynomial when . For all , it is sufficient to prove 2 31 3 3 33 2 () nk k kk xxx xxb δ −+ −+++ −= (6) has exactly one solution over . If is a solution of the Equation (6), then we consider three cases in the following. 1) Case A: . By (6), we have . By the two Equations, we have . So and 22 333 33 kkkk k xx bb δ δδδ −+ =+−−+ . 2) Case B: . By (6), we have . Let , then and . By the three Equations, we have . So 2 3 33 k kk xxb b δ δδ −+ =−+−− . 3) Case C: . By (6), we have . Let , then and . By the three Equations, we have . Hence
G. H. Sun 22 33 33 kkk k xxb b δ δδ −+ =−−− . Let , then in Case C. If Case A occurs, then we have . 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 . The theorem holds. In the above section, we consider permutation polynomials over . In the following, we investigate permu tation polynomials over for an odd prime . Theorem 4 Let , where is a positive integer and be an odd prime. Then 22 1 2 () nik kk pp pp xx xx δ −+ −+++ is a permutation polynomial over for any or . Proof For all , it is sufficient to prove 22 1 2 () nik kk pp pp x xx xb δ −+ −+++= only have a solution over for any or 3. Since the proof is similar for or 2, we only consider . Similarly, the proof is also similar for or 3, so we only consid er . For , if 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 : . Then we have . Hence . Therefore, 2 22 1() 2 k kk p pp xxbb δ δδ −+ =−++ . 2) Case B : . Then we have and . Hence 2 22 1() 2 k kk p pp x xbb δ δδ −+ =−++ . 3) Case C : . Then we have . 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 . For , if 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 : . Then we have . Hence . Therefore, 2 22 1() 2 k kk p pp xxbb δ δδ −+ =−++ . 2) Case B : . Then we have 32 . k kkk ppp p xxxxb δ +− +=− (7) Let . Then raising the th power, th power, and th power on the both sides for Equa tion (7), respectively, we have (8) 32 2kkk k ppp p x xxxu+− += (9)
G. H. Sun (10) Adding (7) to (8), we have (11) Subtracting (10) from (9), we have (12 ) Adding (11) to (12), we have . Hence and 2 32 1() 2 kkk k pppp xx bb δ δδ −+ =−++ . 3) Case C : . Then we have 32 . k kkk ppp p xxxxb δ −−− =−− (13) Let . Raising the 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) (15) ( 16) Subtracting (13) from (14), then we obtain (17) Adding (15) to (16), then we have 3 23 22 . k kk ppp xxv v−−= + (18) Subtracting (18) from (17), then we obtain . Hence and 2 32 1() 2 kkk k pp pp xx bb δ δδ −+ =−+++ . Let . Then 3 22kk kk p ppp bb δδ −+ ++= in the Case C . If Case A occurs, then . Hence 3232 3223 2222 ()()( 0 ) kk kkk k kkkk kkkk kk p ppp pp pp pppppppp bb bb xxxx xxxx δδ δδ δ δδδ = −++=−++ =−−++ =− −−−+−+−=
G. H. Sun 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 . The theorem holds. 3. Conclusion In the paper, we obtain some permutation polynomials of the form with , 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, 750757. [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, 65120. 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, 133146. [4] LaigleChapuy, Y. (2007) Permutation Polynomials and Applications to Coding Theory. Finite Fields and Their Ap plications, 13, 5870. 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, 131151. [7] Cao, X. and Hu, L. (2011) New Methods for Generating Permutation Polynomials over Finite Fields. Finite Fields and Their Applications, 17, 493503. http://dx.doi.org/10.1016/j.ffa.2011.02.012 [8] Charpin, P. and Kyureghyan, G. (2009) When Does Permute . Finite Fields and Their Applications, 15, 615632. 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 . Science in China Series A: Mathematics, 53, 639647. http://dx.doi.org/10.1007/s1142500801428 [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, 492521. 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 Related to Dickson Polynomial s. Finite Fields and Their Applications, 11, 111122. 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, 492521. http://dx.doi.org/10.1016/j.ffa.2011.11.002 [13] Helleseth, T. and Zinoviev, V. (2003) New Kloosterman Sums Identities over for All . Finite Fields and Their Applications, 9, 187193. http://dx.doi.org/10.1016/S10715797(02)00028X [14] Yuan, J. and Ding, C. (2007) Four Classes of Permutation Polynomials of . Finite Fields and Their Applications, 13, 869876. 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 . Fi nite Fields and Their Applications, 14, 482493. 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, 560574. 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 over . Applicable Algebra in Engineering, Communication and Computing, 21, 145150.
G. H. Sun [18] Zha, Z. and Hu, L. (2012) Two Classes of Permutation Polynomials over Finite Fields. Finite Fields and Their Appli cations, 18, 781790. 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, 1623.
