# A Class of New Permutation Polynomials overF2n

Authors: Qian Liu; Ximeng Liu; Jian Zou
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, according to the known results of some normalized permutation polynomials with degree 5 overF2n, we determine sufficient and necessary conditions on the coefficients b1,b2∈F2n2 such that fx=x3x¯2+b1x2x¯+b2x permutes F2n. Meanwhile, we obtain a class of complete permutation binomials over F2n.


---

## Body

## 1. Introduction

DenoteFq as a finite field with q elements, where q is a prime power; then, Fq∗ is its multiplicative group. The bijectivity of the associated polynomial mapping(s) f:x⟼fx from Fq into itself (and fx+x) makes a polynomial fx∈Fqx as a (complete) permutation polynomial [1]. Research interests in (complete) permutation polynomials over finite fields have been aroused due to their widespread applications in cryptography [2, 3], combinatorial designs [4], design theory [1, 5], coding theory [6], and other areas of mathematics and engineering [1, 7]. Readers could refer to [1, 8] for a comprehensive survey about (complete) permutation polynomials. So, it is important to realize that there is significance in discovering new methods to construct permutation polynomials. Readers can find recent progress in [9, 10].Few-term permutation polynomials, especially binomials and trinomials, have not only simple algebraic form but excellent properties. The following form overF2n from Niho exponents has drawn much attention:(1)fx=xr1+b1xs2m−1+b2xt2m−1,where n=2m, r,s,t∈ℤ, b1,b2∈F2n. Note that s,t can be viewed as modulo 2m+1. It is a hard problem to find necessary and sufficient conditions on b1,b2 for (1) being a permutation polynomial over F2n with given r,s,t. In most known cases, the coefficients are assumed to be trivial, such as b1,b2=1,1; some pairs r,s,t in (1) were made in [10–15]. For r,s,t=1,1,2, Hou [16] completely characterized all non-trivial b1,b2 over Fq2 through the Hermite criterion. After that, Tu et al. [17] studied the case over Fq2 where r,s,t=1,2m,2 by solving low-degree equations with variable in the unit circle. The latter only obtained the sufficient conditions but conjectured their necessity based on numerical experiments, which were then proved by Bartoli [18] and Hou [19], respectively, using algebraic curves over finite fields and the Hasse–Weil bound. In 2018, Tu and Zeng [20] determined all b1,b2 with r,s,t=1,2m−1,2n−1 and gave sufficient conditions for r,s,t=1,3⋅22m−2,22m−2 over F2n, the necessity of which was later proved by Hou [21], using a similar method described in [19]. Recently, Zheng et al. [22] claimed sufficient conditions for both r,s,t=1,1,2k2mk−1/2k−12m−1 and r,s,t=1,2k/2k−1,−1/2k−1 over F2n. Furthermore, they conjectured the necessity of the former based on numerical experiments. Very recently, by making use of the similar approach in [18], Bartoli and Timpanella [23] provided necessary conditions for r,s,t=n+m,m,n over finite fields with characteristic 2.To our knowledge, only above seven different pairsr,s,t had been characterized completely. However, the exponents of fx in (1) are also Niho exponents. This motivates us to explore new permutation polynomials with general coefficients b1,b2 from non-Niho exponents with even characteristics. By transforming the problem into studying some normalized permutation polynomials with degree 5 over even characteristics, we determine the coefficients b1,b2 for fx=x3x¯2+b1x2x¯+b2x being a permutation over F2n.The rest of this paper is arranged as follows. Some notations and useful results are presented in Section2. In Section 3, the sufficient and necessary conditions are shown to determine the coefficients of a class of permutation polynomials over F2n. Finally, Section 4 provides some concluding remarks.


## 2. Preliminaries

Letm and n be two positive integers with m|n and F2n be a finite field with 2n elements; the trace function from F2n to F2m is denoted by Trmn⋅, where(2)Trmnx=x+x2m+x22m+⋯+x2n/m−1m.If the usual complex conjugation of anyx∈F22m is defined as x¯=x2m, the following relations hold.(i)
For allx∈F22m, x+x¯∈F2m,xx¯∈F2m.(ii)
For allx,y∈F22m, x+y¯=x¯+y¯,xy¯=x¯y¯.U2m+1 denotes the unit circle of F22m as(3)U2m+1=x∈F22m:x2m+1=xx¯=1.Lemma 1 (see [24]).
fx∈Fqx with f0=0 is a permutation polynomial over Fq iff f:x⟼fx from Fq∗ into itself is a bijection.Hereinafter, we claim thatfx is a permutation polynomial over Fq∗ upon the bijectivity of fx from Fq∗ to Fq∗, which is the only case we consider.Lemma 2 (see [1]).
The irreducibility offx∈Fqx with degree n remains over Fpm iff gcdm,n=1.Definition 1 (see [25]).
A permutation polynomialfx∈Fqx of degree n is said to be normalized if the following properties hold:(i)
fx is monic and the value of fx at 0 is equal to 0.(ii)
The coefficient ofxn−1 equals 0 if p∤n, where p is the characteristic of Fq.Remark 1.
Letb,c∈Fq and a∈Fq∗; for any permutation polynomial fx∈Fqx, there exists a unique normalized form provided by gx=afx+b+c.Theorem 1 (Hermite’s criterion) (see [1]).
Letp be the characteristic of Fq. Thus, fx∈Fqx is a permutation polynomial over Fq iff(i)
fx has exactly one solution over Fq.(ii)
∀t∈ℤ, where 1≤t≤q−2, t≠0modp, the degree of the reduction of fxtmodxq−x is no greater than q−2.From Hermite’s criterion, the characterization of all normalized permutation polynomials with degree no greater than 5 inFq is due to ([1], Section 7.2), and they are listed in Table 1.Table 1
Normalized permutation polynomials with degree no greater than 5 inFq.
Normalized permutation polynomialqxAllqx2Evenqx3q≢1mod3x3−ax (a is not a square of Fq)3|qx4±3xq=7x4+a1x2+a2x (0 is a unique solution in Fq)Evenqx5q≢1mod5x5−ax (a is not a fourth power of Fq)5|qx5+axa2=2q=9x5±2x2q=7x5+ax3±x2+3a2x (a is not a square of Fq)q=7x5+ax3+5−1a2x (all a)q≡±2mod5x5+ax3+3a2x (a is not a square of Fq)q=13x5−2ax3+a2x (a is not a square of Fq)5|q


## 3. A Class of Permutation Polynomials overF2n

In this section, we consider the coefficientsb1,b2∈F2n such that the polynomial fx=x3x¯2+b1x2x¯+b2x permutes over F2n.The main results in this paper are given in the following theorems.Theorem 2.
For two positive integersm and n with n=2m, let b1,b2∈F2n. Define gz=z5+z3b1b1¯+b2+b2¯+z2b1+b1¯b1b1¯+b2+b2¯+b1¯b2+b1b2¯+zb1+b1¯4+b1+b1¯2b1b1¯+b2+b2¯+b2b2¯∈F2mz. Then, the polynomial(4)fx=x3x¯2+b1x2x¯+b2xpermutes F2n iff one of the following two cases holds:(1)
Ifm≡2mod4, gx=x5 permutes F2m.(2)
Ifm is odd, gx=x5+ax3+5−1a2x permutes F2m.Proof.
Based on Lemma1, in order to prove that fx is a permutation polynomial in F2n∗, we only consider that for any c∈F2n∗, the equation(5)x3x¯2+b1x2x¯+b2x=chas exactly one root in F2n∗.
Letx=λy, where λ∈U2m+1 and y∈F2m. Then, equation (5) becomes(6)λy5+b1λy3+b2λy=c.
Raising both sides of equation (6) to the power 2m leads to(7)y5+b1¯y3+b2¯y=λc¯.
Sincec∈F2n∗, we can let c=de, where d∈F2m∗ and e∈U2m+1. Then, equation (7) can be rewritten as(8)y5+b1¯y3+b2¯y=λde−1.
Raising both sides of equation (8) to the power 2m yields(9)y5+b1y3+b2y=λ−1de.
Multiplying equations (8) and (9), we can obtain(10)y10+y8b1+b1¯+y6b1b1¯+b2+b2¯+y4b1¯b2+b1b2¯+y2b2b2¯=d2.
The substitution ofy2 with y in equation (10) leads to(11)y5+y4b1+b1¯+y3b1b1¯+b2+b2¯+y2b1¯b2+b1b2¯+yb2b2¯=d2.
Lety=z+b1+b1¯, and we can get(12)z5+z3b1b1¯+b2+b2¯+z2b1+b1¯b1b1¯+b2+b2¯+b1¯b2+b1b2¯+zb1+b1¯4+b1+b1¯2b1b1¯+b2+b2¯+b2b2¯=constant,where constant=b1b1¯b13+b1¯3+b1+b1¯2b1b2+b1¯b2¯+b1+b1¯b2b2¯+b12b1¯2+d2 and constant∈F2m.
From the above discussion, we can deducefx=x3x¯2+b1x2x¯+b2x permutes F2n iff gz=z5+z3b1b1¯+b2+b2¯+z2b1+b1¯b1b1¯+b2+b2¯+b1¯b2+b1b2¯+zb1+b1¯4+b1+b1¯2b1b1¯+b2+b2¯+b2b2¯ permutes F2m.
Based on Table1, we know that if gz is a normalized permutation polynomial of degree 5 over Fqq=2m, then it must have the following forms:(1)
z5, q≢1mod5.(2)
z5+az3+5−1a2z (a arbitrary), q≡±2mod5.
Whenq≢1mod5, we have 4∤m, which includes that m≡2mod4 and m is odd. When m is odd, that is, q=±2mod5, we mainly study the permutation polynomial of z5+az3+5−1a2z (a arbitrary). When m≡2mod4, we consider the permutation polynomial of z5. Hence, gz permutes F2m iff one of the following two cases holds:(1)
Ifm≡2mod4, gz=z5 permutes F2m.(2)
Ifm is odd, gz=z5+az3+5−1a2z permutes F2m.
In conclusion, we deduce that the polynomial(13)fx=x3x¯2+b1x2x¯+b2xpermutes F2n iff the following two cases are satisfied:(1)
Ifm≡2mod4, gx=x5 permutes F2m.(2)
Ifm is odd, gx=x5+ax3+5−1a2x permutes F2m.Remark 2.
Whenb1 and b2 are both 0, if 4∤m, then gcd2m+1+3,2n−1=1, so we achieve that the monomial fx=x3x¯2 permutes F2n. If b1,b2∈F2n are not both 0, then fx is binomial or trinomial in F2n. We will investigate the permutation behavior of those polynomials in the sequel.Theorem 3.
For two positive integersm and n with n=2m and m being even, let b1,b2∈F2n which are not both 0. Then, the polynomial(14)fx=x3x¯2+b1x2x¯+b2xpermutes F2n iff m≡2mod4, b1=θb2, and b2 is a root of x2+θ−2ωx+θ−4ω=0, where θ∈F2m∗ and ω∈F2m∗ is a primitive third root of unity.Proof.
Based on Theorem2, we deduce that fx=x3x¯2+b1x2x¯+b2x permutes F2n iff gx=x5+x3b1b1¯+b2+b2¯+x2b1+b1¯b1b1¯+b2+b2¯+b1¯b2+b1b2¯+xb1+b1¯4+b1+b1¯2b1b1¯+b2+b2¯+b2b2¯ permutes F2m. When m≡2mod4, we get that fx permutes F2n iff gx=x5 permutes F2m.
“⇒” Comparing the coefficients of gx and x5, we have(15)b1b1¯+b2+b2¯=0,(16)b1b2¯+b1¯b2=0,(17)b1+b1¯4+b2b2¯=0.
From equation (16), we can directly obtain that b1/b2=b1¯/b2¯, i.e., b1/b2∈F2m. Hence, there exists some element θ∈F2m∗ such that b1=θb2.
Pluggingb1=θb2 into equation (15), we have(18)θ2b2b2¯+b2+b2¯=0.
By substitutingb1 with θb2 in equation (17), we obtain(19)θ4b2+b2¯4+b2b2¯=0.
Combining equations (18) and (19), we know that θ12b2b2¯3=1. This means that b2b2¯=θ−4ω and b2+b2¯=θ−2ω, where ω∈F2m∗ is a primitive third root of unity.
Therefore, we conclude thatb2 and b2¯ are exactly two roots of the equation(20)x2+θ−2ωx+θ−4ω=0.
Hence, the above analysis shows that form≡2mod4, if fx permutes F2n, then b1=θb2 and b2 is a root of x2+θ−2ωx+θ−4ω=0, where θ∈F2m∗ and ω∈F2m∗ is a primitive third root of unity.
In what follows, we will proceed to prove the necessity.
“⇐” For some θ∈F2m∗, let b1=θb2, and then we know b1/b2∈F2m∗, and this is equivalent to b1/b2=b1¯/b2¯, which implies that b1b2¯+b1¯b2=0.
Suppose thatb2 and b2¯ are two different roots of equation (20) in F2n\F2m; then, we have b2b2¯=θ−4ω and b2+b2¯=θ−2ω. Recall that b1=θb2, and we have(21)b1b1¯=θ2b2b2¯=θ−2ω,b1+b1¯=θb2+b2¯=θ−1ω,which implies that(22)b1b1¯+b2+b2¯=θ−2ω+θ−2ω=0,b1+b1¯4+b2b2¯=θ−4ω4+θ−4=0,where ω∈F2m∗ is a primitive third root of unity.
Therefore, equations (15)–(17) are satisfied. Furthermore, we know that if m≡2mod4, b1=θb2 and b2 is a root of x2+θ−2ωx+θ−4ω=0, where θ∈F2m∗ and ω∈F2m∗ is a primitive third root of unity, and thus fx is a permutation polynomial over F2n.
To summarize, we conclude that the polynomial(23)fx=x3x¯2+b1x2x¯+b2xpermutes F2n iff m≡2mod4, b1=θb2, and b2 is a root of x2+θ−2ωx+θ−4ω=0, where θ∈F2m∗ and ω∈F2m∗ is a primitive third root of unity.Theorem 4.
For two positive integersm and n with n=2m and m being odd, let b1,b2∈F2n which are not both 0. Then, the polynomial(24)fx=x3x¯2+b1x2x¯+b2xpermutes F2n iff one of the following two cases holds:(1)
b1=0, b2=θω or b2=θω2, where θ∈F2m∗ and ω∈F2n is a primitive third root of unity.(2)
b1=θω or b1=θω2, b2=θ2+θηω2 or b2=θ2+θηω, where θ∈F2m∗, η∈F2m, and ω∈F2n is a primitive third root of unity.Proof.
Based on Theorem2, if m is odd, then fx permutes F2n iff gx=x5+ax3+5−1a2x permutes F2m, where gx=x5+x3b1b1¯+b2+b2¯+x2b1+b1¯b1b1¯+b2+b2¯+b1¯b2+b1b2¯+xb1+b1¯4+b1+b1¯2b1b1¯+b2+b2¯+b2b2¯.
Sincegcd2,m=1, x2+x+1 is a irreducible polynomial in F2, and we deduce that x2+x+1 also remains irreducible over F2m by Lemma 2. Let ω be one of the roots of hx=x2+x+1 in F2n; then, ω2+ω+1=0 and ω is a primitive third root of unity. Furthermore, we can view 1 and ω as a basis of vector space F2n upon F2m.
“⇒” Comparing the coefficients of gx and x5+ax3+5−1a2x, we have(25)b1+b1¯b1b1¯+b2+b2¯+b1¯b2+b1b2¯=0,(26)5−1b1b1¯+b2+b2¯2=b1+b1¯4+b1+b1¯2b1b1¯+b2+b2¯+b2b2¯.
From equation (26), we know that(27)b1b1¯+b2+b2¯2+b1+b1¯4+b1+b1¯2b1b1¯+b2+b2¯+b2b2¯=0.
Then, we can discuss the solutions ofgx=0. as follows.Case 1.
b1=0. Then, equation (27) turns to(28)b2+b2¯2=b2b2¯.
Since 1 andω are basis of vector space F2n upon F2m, for any element b2∈F2n, we can set b2=λ+θω with λ∈F2m,θ∈F2m∗.
By pluggingb2=λ+θω into equation (28), we obtain(29)θ2ω+ω¯2=λ+θωλ+θω¯.
Sincem is odd, we know that ω¯=ω2m=ω2. Then, equation (29) can be written as(30)λ2+λθ=0,which implies that λ=0 or λ=θ. Consequently, we conclude that b2=θω or b2=θω2.
The above analysis indicates that iffx permutes F2n and m is odd, then b1=0, b2=θω or b2=θω2, where θ∈F2m∗ and ω∈F2n is a primitive third root of unity.Case 2.
b1≠0. Thus, equation (25) becomes(31)b1b2+b1¯b2¯=b1b1¯b1+b1¯,and this is equivalent to(32)b1+b2b1¯=b1¯+b2¯b1.
From equation (32), we can directly obtain that b1+b2/b1∈F2m. Hence, there exists some element η∈F2m such that b1+b2/b1¯=η, i.e., b2=b1¯b1+η.
Pluggingb2=b1¯b1+η into equation (27) gives(33)b1+b1¯2η2+b1b1¯b1+b1¯η+b1+b1¯4=b1b1¯η2+b1+b1¯3η+b1b1¯b1+b1¯2.
Comparing the coefficients on both sides of equation (33), we have(34)b1+b1¯2=b1b1¯.
Discussion similar to that in Case1 shows that b1=θω or b1=θω2. Meanwhile, we obtain b2=θ2+θηω2 or b2=θ2+θηω, which follows from b2=b1¯b1+η.
Therefore, the above analysis demonstrates that iffx permutes F2n and m is odd, then b1=θω or b1=θω2, b2=θ2+θηω2 or b2=θ2+θηω, where θ∈F2m∗, η∈F2m, and ω∈F2n is a primitive third root of unity.
All in all, whenm is odd, if the polynomial fx permutes F2n, then one of the following two cases is satisfied:(1)
b1=0, b2=θω or b2=θω2, where θ∈F2m∗ and ω∈F2n is a primitive third root of unity.(2)
b1=θω or b1=θω2, b2=θ2+θηω2 or b2=θ2+θηω, where θ∈F2m∗, η∈F2m, and ω∈F2n is a primitive third root of unity.
Next, we will continue to prove the necessity.
“⇐” If b1=0, b2=θω or b2=θω2, then b1b1¯+b2+b2¯b1+b1¯+b1¯b2+b1b2¯=0, which means that equation (25) is satisfied. Since ω∈F2n is a primitive third root of unity and ω2+ω+1=0, we can calculate that b2+b2¯=θ and b2b2¯=θ2, and thus the left-hand side of equation (27) turns to b2+b2¯2+b2b2¯=θ2+θ2=0, which implies that equation (27) is satisfied. Therefore, when m is odd, we conclude that if b1=0, b2=θω, or b2=θω2, (θ∈F2m∗ and ω∈F2n is a primitive third root of unity), the polynomial fx is a permutation polynomial over F2n.
Ifb1≠0, recall that b1=θω or b1=θω2, b2=θ2+θηω2 or b2=θ2+θηω, and we have(35)b1b1¯=θωθω¯=θ2ω3=θ2,b1+b1¯=θω+θω2=θ,b2+b2¯=θ2+θηω2+θ2+θηω¯2=θηω2+θηω=θη,b2b2¯=θ2+θηω2θ2+θηω¯=θ4+θ3ηω+θ3ηω2=θ2η2,b1¯b2=θω¯θ2+θηω2=θω2θ2+θηω2=θ3ω2+θ2ηω,b1b2¯=θωθ2+θηω¯2=θωθ2+θηω=θ3ω+θ2ηω2,which implies that(36)b1b1¯+b2+b2¯b1+b1¯+b1¯b2+b1b2¯=θ2+θηθ+θ3ω2+θ2ηω+θ3ω+θ2ηω2=θ3+θ2η1+ω+ω2+θ3ω+ω2=θ3+θ3=0,where the third equation holds only if ω2+ω+1=0. Consequently, we conclude that equation (25) is satisfied.
Next we consider(37)b1b1¯+b2+b2¯2+b1+b1¯4+b1+b1¯2b1b1¯+b2+b2¯+b2b2¯=θ2+θη2+θ4+θ2+θηθ2+θ4+θ3ηω+θ3ηω2+θ2η2=θ3η1+ω+ω2=0,where the second equation holds only if ω2+ω+1=0. Hence, we can get that equation (27) is satisfied.
Therefore, the above analysis shows that form is odd, if b1=θω or b1=θω2, b2=θ2+θηω2 or b2=θ2+θηω, where θ∈F2m∗, η∈F2m, and ω∈F2n is a primitive third root of unity, then the polynomial fx permutes F2n.
All in all, form is odd, we know that fx permutes F2n if one of the following two cases is satisfied:(1)
b1=0, b2=θω or b2=θω2, where θ∈F2m∗ and ω∈F2n is a primitive third root of unity.(2)
b1=θω or b1=θω2, b2=θ2+θηω2 or b2=θ2+θηω, where θ∈F2m∗, η∈F2m, and ω∈F2n is a primitive third root of unity.
In conclusion, we deduce that the polynomial(38)fx=x3x¯2+b1x2x¯+b2xpermutes F2n iff one of the following two cases is met:(1)
b1=0, b2=θω or b2=θω2, where θ∈F2m∗ and ω∈F2n is a primitive third root of unity.(2)
b1=θω or b1=θω2, b2=θ2+θηω2 or b2=θ2+θηω, where θ∈F2m∗, η∈F2m, and ω∈F2n is a primitive third root of unity.Applying Theorem4 to b1=0 and θ=1, we have the following.Corollary 1.
For two positive integersm and n satisfying n=2m and m is odd, the binomial fx=x3x¯2+ωx is a complete permutation polynomial over F2n.Remark 3.
Observe that a complete permutation binomialfx proposed in Corollary 1 is obtained by Zieve [26]. However, the approach we used to prove the permutation property is different from that in [26].


## 4. Concluding Remarks

In this paper, by transforming the problem into studying some normalized permutation polynomials of degree five with even characteristics, we investigate the coefficient pairsb1,b2 making fx=x3x¯2+b1x2x¯+b2x to be a permutation polynomial over F2n. The sufficient and necessary conditions are shown in Theorems 3 and 4. Furthermore, a class of complete permutation binomials with the form fx=x3x¯2+ωx over F2n is obtained.



---

*Source: 5872429-2021-11-15.xml*