pith. sign in

arxiv: 2605.21819 · v1 · pith:VUU37XUKnew · submitted 2026-05-20 · 💻 cs.CR

Graph Structure of Chebyshev Permutation Polynomials over Binary and Ternary Adic Rings

Xiaoxiong Lu , Yuling Dai , Chengqing Li This is my paper

Pith reviewed 2026-05-22 08:29 UTC · model grok-4.3

classification 💻 cs.CR
keywords Chebyshev permutation polynomialsfunctional graphscycle structurepath lengthsadic ringsbinary and ternary componentsdynamical complexitycryptographic maps
0
0 comments X

The pith

Chebyshev permutation polynomials over rings of the form 2 to the k1 times 3 to the k2 produce functional graphs with a constant number of cycles of each length and predictable branching as the exponents increase.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives an explicit description of the paths and cycles that appear when the Chebyshev polynomial is iterated on every element of the ring Z_{2^{k1} 3^{k2}}. It reaches this description by first proving new reduction properties of the polynomial modulo powers of 2 and modulo powers of 3, then combining those properties across the two parts of the ring. A reader cares because the resulting graph controls the repetition and transient behavior of the iteration, which in turn determines how suitable the map is for pseudorandom generation or cryptographic primitives. The central finding is that the graph retains strong regularities, such as the same number of cycles of any fixed length regardless of how large k1 and k2 become, and branching factors that follow simple patterns tied to the exponents.

Core claim

Building on newly established properties of Chebyshev polynomials modulo powers of 2 and modulo powers of 3, the functional graph over the composite ring Z_{2^{k1} 3^{k2}} has a constant number of cycles of any given length together with branching patterns that can be predicted directly from the values of k1 and k2. This structure extends earlier characterizations that were available only when the ring was a pure power of a single prime.

What carries the argument

The functional graph whose vertices are the elements of the ring and whose directed edges are given by one application of the Chebyshev polynomial, with its cycle and path counts obtained by lifting the separate behaviors on the 2-power and 3-power components.

If this is right

  • The number of cycles of any length l stays the same once k1 and k2 are large enough.
  • The number of elements that map into a cycle after exactly m steps follows a regular formula governed by the exponents.
  • Transient path lengths before entering cycles become explicitly computable for any starting element.
  • Cryptographic security estimates that rely on the absence of short cycles or on mixing time gain precise quantitative bounds from the cycle counts.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same lifting technique from prime-power cases might apply when the ring includes additional prime-power factors, yielding cycle counts for a wider class of composite moduli.
  • The observed regularity suggests that iteration complexity stays bounded rather than exploding with ring size, which could be checked by comparing period distributions against those of random maps on the same domain.
  • Explicit formulas for the number of fixed points or short cycles could be used to bound the linear complexity of sequences generated by repeated application of the polynomial.

Load-bearing premise

The newly established properties of Chebyshev polynomials modulo powers of 2 and modulo powers of 3 are valid and sufficient to determine the cycle and path structure over the composite ring.

What would settle it

Direct enumeration of all cycles in the functional graph for small concrete values such as k1=2 and k2=1, followed by a count of cycles of some fixed length l that differs from the constant number claimed by the characterization.

Figures

Figures reproduced from arXiv: 2605.21819 by Chengqing Li, Xiaoxiong Lu, Yuling Dai.

Figure 1
Figure 1. Figure 1: Functional graphs of Chebyshev polynomial [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Functional graphs of Chebyshev polynomial [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies the functional graphs of Chebyshev permutation polynomials over the ring Z_{2^{k1} 3^{k2}} (k1, k2 positive integers, with the stated convention on zero). Building on newly derived properties of these polynomials modulo powers of 2 and of 3, it uses the Chinese Remainder Theorem to give an explicit characterization of path lengths, cycle structures, the number of cycles of each length, and the branching patterns that appear as the exponents k1 and k2 grow.

Significance. If the claimed characterizations hold, the work supplies a precise, regular description of the dynamics of these maps over composite adic rings. The constant cycle counts per length and the predictable lifting rules follow directly from the product structure under CRT once the prime-power cases are settled; this supplies concrete, falsifiable information useful for cryptographic security arguments that rely on the iteration complexity of nonlinear maps.

minor comments (2)
  1. Abstract, line 3: the phrase “0∈{k1,k2}” is ambiguous; clarify whether it means that at least one of k1 or k2 is positive, or whether the zero-exponent cases are included as base rings.
  2. The manuscript would benefit from an explicit statement (perhaps in §3 or §4) of the precise lifting rules that relate the cycle index at exponent k to the index at exponent k+1; the current description is consistent with the product structure but the formulas are not written out.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our work and for the positive assessment of its significance for cryptographic applications. The recommendation for minor revision is noted; however, the report does not list any specific major comments requiring clarification or correction.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper first derives explicit properties of Chebyshev polynomials modulo 2^{k1} and modulo 3^{k2} separately using direct algebraic analysis of the functional graphs over prime-power rings. These component results are then combined via the Chinese Remainder Theorem, which induces a product structure on the graph over Z_{2^{k1}3^{k2}}. Cycle lengths are obtained as LCMs of the component periods and the constant cycle counts per length follow directly from the constancy already established on each prime-power component; no parameter is fitted to the composite data and no step invokes the final claim to justify an earlier one. The branching and lifting rules for increasing exponents are likewise derived from the prime-power cases without circular appeal.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim depends on the validity of newly stated reduction properties of Chebyshev polynomials modulo 2^k and 3^m; these properties are treated as established background rather than derived within the paper.

axioms (1)
  • domain assumption New properties of Chebyshev polynomials modulo powers of 2 and 3 hold and extend to the composite ring.
    The abstract states that the characterization builds directly on these new properties.

pith-pipeline@v0.9.0 · 5739 in / 1189 out tokens · 77618 ms · 2026-05-22T08:29:12.167276+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Dynamic analysis of digital chaotic maps via state-mapping networks,

    C. Li, B. Feng, S. Li, J. Kurths, and G. Chen, “Dynamic analysis of digital chaotic maps via state-mapping networks,” IEEE Transactions on Circuits and Systems I: Regular Papers , vol. 66, no. 6, pp. 2322–2335, 2019

    work page 2019

  2. [2]

    A image encryption scheme based on dynamical perturbation and linear feedback shift register,

    X.-J. Tong, M. Zhang, Z. Wang, and Y . Liu, “A image encryption scheme based on dynamical perturbation and linear feedback shift register,” Nonlinear Dynamics, vol. 78, no. 3, pp. 2277–2291, 2014

    work page 2014

  3. [3]

    Theoretical design and FPGA-based implementation of higher- dimensional digital chaotic systems,

    Q. Wang, S. Yu, C. Li, J. L ¨u, X. Fang, C. Guyeux, and J. M. Bahi, “Theoretical design and FPGA-based implementation of higher- dimensional digital chaotic systems,” IEEE Transactions on Circuits and Systems I: Regular Papers , vol. 63, no. 3, pp. 401–412, 2016

    work page 2016

  4. [4]

    Hyperchaotic bilateral random low-rank approximation random sequence generation method and its application on compressive ghost imaging,

    S. Tan, J. Sun, Y . Tang, Y . Sun, and C. Wang, “Hyperchaotic bilateral random low-rank approximation random sequence generation method and its application on compressive ghost imaging,”Nonlinear Dynamics, vol. 112, no. 7, pp. 5037–5052, 2024

    work page 2024

  5. [5]

    Period distribution of the generalized discrete Arnold Cat map for n = 2 e,

    F. Chen, K.-W. Wong, X. Liao, and T. Xiang, “Period distribution of the generalized discrete Arnold Cat map for n = 2 e,” IEEE Transactions on Information Theory , vol. 59, no. 5, pp. 3249–3255, 2013

    work page 2013

  6. [6]

    On the security of public-key algorithms based on Chebyshev polynomials over the finite field Zn,

    X. Liao, F. Chen, and K.-W. Wong, “On the security of public-key algorithms based on Chebyshev polynomials over the finite field Zn,” IEEE Transactions on Computers, vol. 59, no. 10, pp. 1392–1401, 2010

    work page 2010

  7. [7]

    Periodicity analysis of Logistic map over ring Z3n ,

    X. Lu, E. Y . Xie, and C. Li, “Periodicity analysis of Logistic map over ring Z3n ,” International Journal of Bifurcation and Chaos , vol. 33, no. 5, p. art. no. 2350063, 2023

    work page 2023

  8. [8]

    Periodic properties of commutative polynomials defined by fourth order recurrence relations with two variables over Z2k ,

    D. Yoshioka, “Periodic properties of commutative polynomials defined by fourth order recurrence relations with two variables over Z2k ,” in IEEE International Symposium on Information Theory , 2023, pp. 1425– 1429

    work page 2023

  9. [9]

    D. E. Knuth, The Art of Computer Programming, Volume 2: Seminu- merical Algorithms, 3rd ed. Reading, Massachusetts: Addison-Wesley Professional, 1997

    work page 1997

  10. [10]

    Public-key encryption based on chebyshev maps,

    L. Kocarev and Z. Tasev, “Public-key encryption based on chebyshev maps,” in Proceedings of the 2003 International Symposium on Circuits and Systems, 2003. ISCAS ’03. , vol. 3, 2003, pp. III–III

    work page 2003

  11. [11]

    Security of public-key cryptosystems based on Chebyshev polynomials,

    P. Bergamo, P. D’Arco, A. D. Santis, and L. Kocarev, “Security of public-key cryptosystems based on Chebyshev polynomials,” IEEE Transactions on Circuits and Systems I: Regular Papers , vol. 52, no. 7, pp. 1382–1393, 2005

    work page 2005

  12. [12]

    Security analysis of the public key algorithm based on Chebyshev polynomials over the integer ring Zn,

    F. Chen, X. Liao, T. Xiang, and H. Zheng, “Security analysis of the public key algorithm based on Chebyshev polynomials over the integer ring Zn,” Information Sciences, vol. 181, no. 22, pp. 5110–5118, 2011

    work page 2011

  13. [13]

    The graph structure of Cheby- shev permutation polynomials over ring Zpk ,

    C. Li, X. Lu, K. Tan, and G. Chen, “The graph structure of Cheby- shev permutation polynomials over ring Zpk ,” IEEE Transactions on Information Theory, vol. 71, no. 2, pp. 1419–1433, 2025

    work page 2025

  14. [14]

    The graph structure of Chebyshev polyno- mials over finite fields and applications,

    C. Qureshi and D. Panario, “The graph structure of Chebyshev polyno- mials over finite fields and applications,” Designs, Codes and Cryptog- raphy, vol. 87, pp. 393–416, 2019

    work page 2019

  15. [15]

    Properties of Chebyshev polynomials modulo pk,

    D. Yoshioka, “Properties of Chebyshev polynomials modulo pk,” IEEE Transactions on Circuits and Systems II: Express Briefs , vol. 65, no. 3, pp. 386–390, 2018

    work page 2018

  16. [16]

    Security of public-key cryptosystems based on Chebyshev polynomials over Z/pkZ,

    D. Yoshioka, “Security of public-key cryptosystems based on Chebyshev polynomials over Z/pkZ,” IEEE Transactions on Circuits and Systems II: Express Briefs , vol. 67, no. 10, pp. 2204–2208, 2020

    work page 2020

  17. [17]

    Fixed-point lifting and ghost periodic points for chebyshev polynomials modulo odd prime powers,

    C. Panraksa and A. Tangboonduangjit, “Fixed-point lifting and ghost periodic points for chebyshev polynomials modulo odd prime powers,” 2026

    work page 2026

  18. [18]

    Periodic properties of chebyshev poly- nomial sequences over the residue ring Z/2kZ,

    D. Yoshioka and K. Kawano, “Periodic properties of chebyshev poly- nomial sequences over the residue ring Z/2kZ,” IEEE Transactions on Circuits and Systems II: Express Briefs , vol. 63, no. 8, pp. 778–782, 2016

    work page 2016

  19. [19]

    Some new properties of the Chebyshev polynomials and their use in analysis and design of dynamic systems,

    Y . G. Bulychev and E. Y . Bulycheva, “Some new properties of the Chebyshev polynomials and their use in analysis and design of dynamic systems,” Automation and Remote Control , vol. 64, no. 4, pp. 554–563, 2003

    work page 2003

  20. [20]

    Key exchange by Chebyshev polynomials modulo 2w,

    K. Umeno, “Key exchange by Chebyshev polynomials modulo 2w,” in Proceedings of Indonesia Cryptology and Information Security , 2005, pp. 95–97

    work page 2005

  21. [21]

    On some properties of Chebyshev poly- nomial sequences modulo 2k,

    D. Yoshioka and Y . Dainobu, “On some properties of Chebyshev poly- nomial sequences modulo 2k,” Nonlinear Theory and Its Applications , vol. 6, no. 3, pp. 443–452, 2015

    work page 2015