Graph Structure of Chebyshev Permutation Polynomials over Ring Zpk

Chengqing Li, Xiaoxiong Lu*, Kai Tan, Guanrong Chen

*Corresponding author for this work

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

3 Citations (Scopus)

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 languageEnglish
Pages (from-to)1419-1433
JournalIEEE Transactions on Information Theory
Volume71
Issue number2
Online published24 Dec 2024
DOIs
Publication statusPublished - Feb 2025

Research Keywords

  • Chebyshev polynomial
  • cycle distribution
  • functional graph
  • period distribution
  • permutation polynomial
  • polynomial congruence
  • pseudo-random number sequence
  • sequence analysis

Fingerprint

Dive into the research topics of 'Graph Structure of Chebyshev Permutation Polynomials over Ring Zpk'. Together they form a unique fingerprint.

Cite this