Abstract
Understanding the underlying graph structure of a nonlinear map over a particular domain is essential in evaluating its potential for real applications. In this paper, we investigate the structure of the associated functional graph of Chebyshev permutation polynomials over a ring Zpk, with p being a prime number greater than three, where 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 and explicit form of the length of a path starting from any given vertex. Then, we show that the functional graph's strong patterns indicate that the number of cycles of any given length always remains constant as k increases. Moreover, we rigorously prove the rules on the elegant structure of the functional graph and verify them experimentally. Our results could be useful for studying the emergence mechanism of the complexity of a nonlinear map in digital computers and security analysis of its cryptographic applications. © 2024 IEEE.
Original language | English |
---|---|
Pages (from-to) | 1419-1433 |
Journal | IEEE Transactions on Information Theory |
Volume | 71 |
Issue number | 2 |
Online published | 24 Dec 2024 |
DOIs | |
Publication status | Published - Feb 2025 |
Research Keywords
- Chebyshev polynomial
- cycle distribution
- functional graph
- period distribution
- permutation polynomial
- polynomial congruence
- pseudo-random number sequence
- sequence analysis