turkmath.org

Index and Carlitz rank are two important measures for the complexity of a permutation polynomial $f(x)$ over the finite field $F_q$. In particular, for cryptographic applications we need both, a high Carlitz rank and a high index. In this article we study the relationship between Carlitz rank $Crk(f)$ and index $Ind(f)$. More precisely, if the permutation polynomial is neither close to a polynomial of the form ax nor a rational function of the form $ax^{-1}$, then we show that $Crk(f) > q-max\{3Ind(f),(3q)^{1/2}\}$. Moreover we show that the permutation polynomial which represents the discrete logarithm guarantees both a large index and a large Carlitz rank. (Joint work with A. Winterhof)