Graph Structure of Chebyshev Permutation Polynomials over Binary and Ternary Adic Rings
This provides theoretical insights for cryptographers analyzing the security of nonlinear maps used in pseudorandom generation and cryptographic applications.
The paper characterizes the functional graph structure of Chebyshev permutation polynomials over mixed-radix rings Z_{2^{k1}3^{k2}}, showing strong regularities such as constant cycle counts and predictable branching patterns despite the complexity of binary and ternary components.
Understanding the functional graph of a nonlinear map over a finite domain is crucial for analyzing its dynamical complexity and potential applications in cryptography and pseudorandom generation. In this paper, we investigate the graph structure of Chebyshev permutation polynomials over the ring $\mathbb{Z}_{2^{k_1}3^{k_2}}$, where $k_1$ and $k_2$ are positive integers and $0\in\{k_1, k_2\}$. Each element of the ring is regarded as a vertex, and the mapping relation defined by the polynomial corresponds to a directed edge. Building on new properties of Chebyshev polynomials modulo powers of $2$ and $3$, we provide an explicit characterization of path lengths and cycle structures in the functional graph. We show that, despite the complexities introduced by the binary and ternary components, the graph exhibits strong regularities, including a constant number of cycles of a given length and predictable branching patterns as $k_1$ and $k_2$ increase. Our results extend previous studies over prime-power rings, offering insights into the emergence of complexity in digital nonlinear maps and supporting the security analysis of their cryptographic applications.