Determining the cycle structure of permutation polynomials of shape x t + γTr (x k)

Abstract

In this thesis we study the cycle structure of permutation polynomials. They play an important role in many applications of finite fields. Of particular note are combinatorial design theory, cryptography and coding theory. An important application of permutation polynomials with known cycle structure in coding theory is their use as parts of turbo codes. In this context we want the permutations to be given as polynomials, because this reduces the implementation cost. But we also want to know their cycle structures, because they give us important algebraic and combinatorial properties of the permutations, which strongly in uence the performance of the final code. Currently we know the cycle structure only for a few simple classes of permutation polynomials. These are monomials, Dickson and linearized polynomials. We give a survey of these results. None of these classes make full use of the structure of a finite field and mainly depend on either the multiplicative or additive group of the field. We focus on permutation polynomials of shape Xt+ Trqn=q(Xk) 2 Fqn[X], where

2 Fqn and 1 t; k qn-1. In contrast to those classes, for which the cycle structure is already known, these depend on both the additive and multiplicative structure of a finite field, but still have a nice algebraic form. Permutation polynomials of this shape were first considered in 2008 by Charpin and Kyureghyan [5] for q = 2, where a complete classification was given. We show, that polynomials of shape Xt+ f(X), where f : Fqn -> Fq, can only be permutations if gcd(t; qn - 1) = 1. In this case Xt is also a permutation, so for classification purposes it suffces to consider t = 1. In recent years Kyureghyan and Zieve [11], Ma and Ge [16] and Li, Qu, Chen, and Li [13] have constructed 24 infinite families of permutation polynomials of shape X + Trqn=q(Xk). We give the number of fixed points for all of these permutations. Further we show that permutation polynomials of shape X + f(X), where f : Fqn -> Fq, are precisely those that also permute any line + Fq, 2 Fqn. We give a condition on f, under which certain of these induced permutations on lines have the same cycle structure. All 17 of the 24 infinite families, where n is fixed to 2 or 3 satisfy this condition. In particular, if n = 2, which holds for 15 of them, this allows us to ascertain the cycle structure by determining it on Fq and any one other line + Fq. The cycle structure on Fq can be found easily, but getting the cycle structure on one of the other lines is still a very difficult problem. We solve it for two families completely and for one family in a special case.