Carlitz rank and index of permutation polynomials

摘要

Carlitz rank and index 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{3d(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. (C) 2017 Published by Elsevier Inc.