The Graph Structure of Chebyshev Permutation Polynomials over Ring $\mathbb{Z}_{p^k}$

Understanding the underlying graph structure of a nonlinear map over a certain domain is essential to evaluate its potential for real applications. In this paper, we investigate the structure of the associated \textit{functional graph} of Chebyshev permutation polynomials over ring $\mathbb{Z}_{p^k}$, where $p$ is a prime number larger than three, every number in the ring is considered as a vertex and the existing mapping relation between two vertices is regarded as a directed edge. Based on some new properties of Chebyshev polynomials and their derivatives, we disclose how the basic structure of the functional graph evolves with respect to parameter $k$. First, we present a complete explicit form of the length of a path starting from any given vertex, i.e., the least period of the sequence generated by iterating a Chebyshev permutation polynomial from an initial state. Then, we show that the strong patterns of the functional graph, e.g., the number of cycles of any given length, is always preserved as $k$ increases. Moreover, we rigorously prove the elegant structure of the functional graph and verify it experimentally. Our results could be useful for studying emergence of complexity of a nonlinear map in digital computer and security analysis of its cryptographical applications.