Constructions Of Permutation Polynomials And Computations Of Their Compositional Inverses Over Finite Fields

The study of permutation polynomials over finite fields is a very crucial constitution of the study area of finite fields,and has wide and significant applications in cryptog-raphy,coding theory and combinatorics.Therefore,it is very meaningful to construct permutation polynomials over finite fields.On the other hand,the study of compositional inverses of a given permutation polynomials over finite fields is a classical and difficult subject which is also an important area to learn in the study of permutation polynomials due to their important applications in cryptography.However,up to now,there is not a general and effective method to construct permutation polynomials over finite fields and only a few special classes of permutation polynomials over finite fields have their explicit compositional inverses,although permutation polynomials have been studied for a long time.In this thesis,we devote to the problems of constructing permutation polynomials over finite fields and computing the compositional inverse of a special class of permuta-tion polynomials over finite fields.The main results are as follows:(1)Permutation trinomials over finite fields consititute an active research due to their simple algebraic form,additional extraordinary properties and their wide applica-tions in many areas.Using the fractional approach,the Hou method and the Dob-bertin method,we obtain ten classes of permutation trinomials over F22k,F32k and F23k respectively,enriching the known results.(2)The trace function is often used in constructing permutation polynomials over finite fields due to its good properties.We consider new permutation polynomials of the form cx+Ti2kl/2k(xa)over F2kl.First of all,by using Magma,we find all permu-tation polynomials over F2kl of the form cx+Tr2kl/2k(xa)with k>1,kl<14,c ? Fql*and a ?[1,ql-2].After analyzing these experiment examples,we present fifteen new classes of permutation polynomials of the form cx+Tr2kl/2k(xa)over F2kl,which explain most of the examples.The methods we use include the approach of substitution,the fractional approach and the Dobbertin method.(3)Recently,several authors have studied permutation trinomials of the form xrh(xq-1)over Fq2.where q is even.We characterize the permutation polynomials of the form xrh(xq-1)over Fq2.where q is an arbitrary prime power.Using AGW Criterion twice,one is multiplicative and the other is additive,we reduce the problem of proving permutation polynomials f(x)=xrh(xq-1)over Fq2 into that of showing corresponding rational permutations R(a)over a small subset S of a proper subfield Fq,which is significantly different from previously known methods.In particular,we demonstrate our method by constructing many new explicit classes of permuta-tion polynomials of the form xrh(xq-1)over Fq2.Moreover,we can explain most of the known permutation trinomials with the same form over finite fields with even characteristic.(4)The study of computing compositional inverses of permutation polynomials over finite fields has attracted a lot of attention due to its applications in theory(e.g.Bent functions and their dual bent functions)and practice(e.g.S-box).We intro-duce a new approach to explicitly computing the compositional inverses of per-mutation polynomials with the form of xrh(xs)over Fq,where s |q-1 and gcd(r,q-1)=1.The main idea relies on a commutative diagram,transforming the problem of computing the compositional inverses of permutation polynomials over Fq into computing the compositional inverses of two restricted permutation mappings,where one of them is a monomial over the finite field and the other is the corresponding fractional polynomial xrh(x)s over a particular subgroup with order(q-1)/s.As consequences,many explicit compositional inverses of permutation polynomials are obtained using this method.