turkmath.org

Carlitz rank and index are two important measures for the complexity of a permutation polynomial. 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 and index. 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 the Carlitz rank is $q+O(\ell+q^{1/2})$, where $\ell$ is its index.