Paper Menu >>
Journal Menu >>
 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 Email: [email protected] m 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. |