IEEE TRANSACTIONS
1
Graph Structure of Chebyshev Permutation Polynomials over Binary and Ternary Adic Rings
arXiv:2605.21819v1 [cs.CR] 20 May 2026
Xiaoxiong Lu, Yuling Dai, Chengqing Li
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 Z2k1 3k2 , where k1 and k2 are positive integers and 0 ∈ {k1 , k2 }. 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 k1 and k2 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. Index Terms—Chebyshev polynomial, graph structure, pseudorandom number sequence, period distribution.
I. I NTRODUCTION
D
Igital computing environments are inherently constrained by discrete state spaces and finite word lengths. When nonlinear systems defined on continuous domains, typically represented by the Logistic map, are implemented on digital hardware, their original complex dynamical characteristics inevitably degrade due to finite-precision effects in floatingpoint or fixed-point arithmetic. This degradation manifests as periodic outputs and statistical deviations from ideal chaotic behavior, ultimately compromising security and the quality of randomness [1]. To mitigate dynamical degradation, prior studies employ external interventions to sustain system complexity. Typical strategies include paralleling multiple nonlinear systems [2], injecting random perturbations into generated sequences [3], and dynamically controlling parameters [4]. However, compared to these remedial strategies, a more fundamental approach is to forgo approximating continuous systems and instead reconstruct nonlinear maps over discrete algebraic structures, such as finite fields or finite rings [5]– [7]. Discrete nonlinear systems inherently preclude the dynamical degradation induced by finite-precision computation This work was supported by the National Natural Science Foundation of China (no. 62571470). X. Lu is with the College of Mathematics and Statistics, Hengyang Normal University, Hengyang, 421008, China. Y. Dai and C. Li are with the School of Computer Science, Xiangtan University, Xiangtan 411105, Hunan, China.
due to their finite state spaces. Furthermore, these systems facilitate exact graph-theoretic and algebraic analyses of key dynamical features, including global period distributions and local evolutionary behaviors. Notably, the residue class ring Zm is predominantly employed for such analyses owing to its structural naturalness. Notably, when the modulus is chosen as m = 2k , fixedpoint integers are naturally represented as k-bit elements in the ring Z2k . This algebraic structure directly corresponds to the arithmetic logic of k-bit registers in modern digital computers, where addition and multiplication operations naturally satisfy the closure property modulo 2k . Compared to executing modular arithmetic over the finite field Zp , nonlinear iterations over Z2k leverage the hardware-level natural overflow mechanism to achieve extremely high computational efficiency [8]. Therefore, discrete nonlinear systems constructed over the ring Z2k , such as various linear and nonlinear congruential generators, constitute the cornerstone of pseudorandom number generation in modern operating systems and standard libraries. Beyond the mainstream binary architecture, the scenario in which the modulus is chosen as m = 3k also has profound scientific significance. Examining from the fundamental dimension of information theory, the hardware complexity required to store an integer N is proportional to r · logr N , where r denotes the radix. The extremum of this function is located at e ≈ 2.718, and among all integers, 3 is the closest to e. This implies that, at the theoretical level, ternary logic exhibits higher storage density and a simpler interconnection topology than binary logic [9]. In this paper, we call finite binary and ternary adic rings as Z2k and Z3k , respectively. Chebyshev polynomials can provide near-optimal polynomial approximations, forming the foundation for stable and rapidly convergent methods in function approximation, interpolation, and the numerical solution of linear systems. The fundamental recurrence relation of Chebyshev polynomials can be expressed as Tn (x) = 2xTn−1 (x) − Tn−2 (x). Their inherent semigroup property serves as a fundamental mechanism for their widespread applications, which is formulated as Tn (Tm (x)) = Tnm (x). With the ongoing evolution of nonlinear dynamics and digital cryptographic systems, Chebyshev polynomials occupy an irreplaceable central position, particularly in public-key encryption mechanisms and pseudorandom sequence design [10]. Early relevant discussions predominantly focused on continuous Chebyshev polynomials over real or complex fields. Specifically, when x ∈ [−1, 1], this polynomial can be explic-
0018-9448 ©2025 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications standards/publications/rights/index.html for more information. Friday 22nd May, 2026 (00:21)
IEEE TRANSACTIONS
2
itly defined through inverse trigonometric functions, and its analytical expression is equivalently represented as Tn (x) = cos(n arccos x). However, cryptanalytic techniques such as phase space reconstruction, chosen-plaintext attacks, and orbital parameter deciphering have compromised various continuous-domain Chebyshev encryption protocols [11], [12]. These vulnerabilities highlight the inherent theoretical and security limitations of continuous chaotic systems in physical implementations. To address the inherent finite-precision effects of continuous chaotic systems in engineering implementations, the academic community has gradually shifted its research focus toward discrete algebraic systems. Researchers have extensively explored Chebyshev polynomials defined over finite fields FN and residue class rings ZN [6], [13]–[15], where N is an integer. Under these conditions, the Chebyshev polynomial is formulated as Tn (x) = 2xTn−1 (x) − Tn−2 (x) mod N.
(1)
In these discrete algebraic structures, Chebyshev polynomials not only perfectly preserve the original semigroup property but also eliminate the precision loss issues caused by floatingpoint operations [6]. Particularly over the residue class ring of prime powers Zpk , Chebyshev permutation polynomials exhibit more complex algebraic structures and exceptionally superior cryptographic properties [12]. When the degree n of the polynomial and the characteristic of the residue ring satisfy specific coprime conditions, the Chebyshev polynomial constitutes a strict permutation polynomial. This indicates that the mapping f (x) ≡ Tn (x) (mod pk ) over the residue class ring Zpk possesses a perfect global bijective property. Despite mitigating dynamical degradation, discrete Chebyshev maps remain vulnerable [16]. Improper choices of the polynomial degree n or the initial state x0 lead to extremely short periods or concentrated fixed points, exposing topological vulnerabilities. Consequently, functional graph analysis has emerged as a core methodology for screening longperiod orbits and ensuring the security of discrete Chebyshev cryptosystems. Furthermore, extensive theoretical studies have quantitatively characterized the permutation rules, period distributions, and trajectory lengths of Chebyshev polynomials across various discrete algebraic structures. As illustrated in Table I, Daniel et al. systematically provided the criteria for the period T of Chebyshev polynomials over the finite field Fq and its corresponding effective number of orbits NT [14]. Breaking through the limitations of prime fields, Li et al. further derived more complex periodic structures and counting formulas over the prime power residue class ring Zpk [13]. Meanwhile, for the prime residue ring ZN , Liao et al. detailed the mapping relationship between the reducibility of the characteristic polynomial f (t) = t2 −2xt+1 ∈ ZN [t] and the corresponding period T ′ [6]. To clarify the notations utilized in Table I, the corresponding symbols are explicitly defined. The variables T and T ′ represent the minimum positive integers satisfying Tns (x) = Tns+T (x) for any positive integer s and element x in the corresponding domain, and Tn (x) = Tn+T ′ (x) for any positive integer n and element x,
respectively. The symbol φ denotes Euler’s totient function, N indicates a positive prime, and õd (n) characterizes the order of n within the quotient group Z∗N /{1, −1}. Furthermore, the auxiliary parameters are determined by the mathematical expressions Ns = min{i | Tni (x) ≡ x0 (mod p)}, ls = 2 ord Tn′ Ns (x0 ) , and w = νp (n2·ord(n ) − 1). Recently, Panraksa and Tangboonduangjit [17] investigated the non-permutation dynamical behavior of Chebyshev polynomials over Zpk . However, this theoretical framework fails to encompass the cases of the rings Z2k and Z3k . For p = 2, although Yoshioka [18] explored the periodic properties of the sequences, their work did not provide explicit expressions for the periods nor a precise characterization of the points from a global topological perspective. Given the limitations of conventional methods in these low-order cases, this paper bridges this theoretical gap by treating Z2k and Z3k as independent algebraic structures and systematically analyzing them separately. Moreover, this paper derives the explicit expressions for the periods and the precise characterization of points over the ring Z2k , and thoroughly reveals the complete functional graph structure and period distribution over the ring Z3k . TABLE I: Conclusions regarding the period distribution of sequences generated by Chebyshev polynomials in the literature [14], [13], and [6] Reference [14]
T or T ′ õd (n)
Condition d > 2 and (d | (q − 1) or d | (q + 1)) q is an odd number q is an even number k≥1
1 Ns
[13]
NT or NT ′
w+1≥k ≥1
Ns · ls
k >w+1
[6]
Ns ls pt 1 2 T ′ ∈ {d : d | N − 1, d > 2} T ′ ∈ {d : d | N + 1, d > 2}
k >w+1 x=1 x=N −1 x ̸= ±1, f (t) is reducible x ̸= ±1, f (t) is irreducible
φ(d) 2õd (n)
1 2 1 pk−1 −1 ls pw −1 ls (p−1)pw−1 ls
1 1 φ(T ′ ) 2
II. P RELIMINARIES To make the analysis on the periodic change process of the Chebyshev polynomial sequence complete, the previously known results about the Chebyshev polynomial are briefly introduced in this section. Chebyshev polynomials of degree n are recursively defined by Tn (x) = 2xTn−1 (x) − Tn−2 (x), (2) where T0 (x) = 1, T1 (x) = x, x ∈ [−1, 1] and n is an integer lager than one. The power series form of Chebyshev polynomials of degree n can be represented as ⌊n/2⌋
n X (n − i − 1)! Tn (x) = (−1)i (2x)n−2i , 2 i=0 i!(n − 2i)!
(3)
where n ≥ 1 [19]. Chebyshev polynomials exhibit a significant semigroup property. When these polynomials are evaluated over the residue ring Zpk , this property is preserved, meaning that for any two positive integers m and n, one has Tn (Tm (x)) ≡ Tm (Tn (x)) ≡ Tm·n (x)
(mod pk ).
IEEE TRANSACTIONS
3
Thus, the composition of N Chebyshev polynomials Tn (x) can be denoted TnN (x) or TnN (x). A Chebyshev integer sequence Spk (x0 ; n) is generated by iterating the Chebyshev polynomial over Zpk . Namely, given an initial value x, the result of i-th iteration is
for any m ≥ 2, where w = max{ν2 (n − 1), ν2 (n + 1)}. Proof. The m-order derivative of Chebyshev polynomials Tn (x) with x = ±1 can be expressed Tn(m) (±1) = (±1)n+m
Tni (x) = Tn (Tni−1 (x)) mod pk , where i ≥ 1 and Tn0 (x) = x mod pk . The least period L(n, p, k, x) of the sequence Spk (x0 ; n) is the minimum possible positive integer of N satisfying TnN (x) ≡ x mod pk . The Chebyshev polynomial Tn (x) is a permutation polynomial modulo pk if and only if gcd(n, p) = gcd(n, p2 − 1) = 1,
(4)
where gcd denotes the greatest common divisor of two integers [15]. For p = 2, the necessary and sufficient condition for Tn (x) to be a permutation polynomial simplifies to n being an odd integer [20]. Similarly, for p = 3, the condition reduces to n ≡ ±1 (mod 6). III. T HE P ERIOD P ROPERTIES OF C HEBYSHEV I NTEGER S EQUENCE This section investigates the distribution of periods for sequences generated through the iteration of Chebyshev permutation polynomials over the rings Zpk , where p ∈ {2, 3}. Given that n is an odd integer, it follows that 2 | (n ± 1). Defining w = max{νp (n − 1), νp (n + 1)} for p ∈ {2, 3}, the inequality w ≥ 2 holds for the specific case where p = 2 and n ≥ 2. Consequently, the p-adic valuation of n2 − 1 satisfies ν2 (n2 − 1) ≥ w + 1 for p = 2, and the exact relation ν3 (n2 − 1) = w is established for p = 3. A. The Period Properties of Chebyshev Integer Sequence over Ring Z2k Lemma 1 and Lemma 2 characterize the multiplicity of the factor 2 within the derivatives at the endpoints and the coefficients of the polynomials. Building upon these results, Theorem 1 illustrates the evolution of sequence periods. Congruence Tn (x0 ) ≡ x0 (mod 22 ) (5) can be verified as follows. When x0 ≡ 1 (mod 4), the identity Tn (1) = 1 immediately implies that congruence (5) holds. When x0 ≡ 2 (mod 4), since T1 (2) = 2 and the recurrence relation Tn (2) ≡ −Tn−2 (2) (mod 4), it follows that congruence (5) holds in this case as well. When x0 ≡ 3 (mod 4), the identity Tn (−1) = (−1)n = −1 gives the same result, and congruence (5) holds. For the case x0 ≡ 0 (mod 4), the congruence can be confirmed through computational checks. Therefore, s ≥ 2 in Theorem 1. Based on the identified periodic patterns, Theorem 1 further establishes explicit expressions for the sequences. Lemma 1. As for any Chebyshev polynomial Tn (x), one has 2w+1 | Tn′ (±1) − 1 and m
2w+⌊ 2 ⌋ | Tn(m) (±1)
(6)
m−1 Y
n2 − j 2 2j + 1 j=0
(7)
for any m, one has Tn′ (±1) = n2 . From the definition of w and n is odd, one has ν2 (n2 − 1) = ν2 (n + 1) + ν2 (n − 1) ≥ w + 1,
(8)
yielding that 2w+1 | (n2 −1). In (7), one has 2 | (n2 −j) when m−1 Q m (n2 − j 2 ). It j is odd from n is odd. It means 2⌊ 2 ⌋−1 | j=2 m
yields from (7) and 2w+1 | (n2 − 1) that 2w+⌊ 2 ⌋ | T (m) (±1) for any m ≥ 2. Lemma 2. As for any Chebyshev polynomial Tn (x), one has 2w | (a1 − 1) and 2w | ai , where w = max{ν2 (n − 1), ν2 (n+1)}. ai denotes the coefficient of xi in the Chebyshev polynomial and i ∈ {3, 5, · · · , n}. Proof. Set n − 2i = 2j + 1 in (3), one has (n−1)/2
n+2j−1 ! n−1 (−1) 2 +j n−2j−1 2 (2x)2j+1 , !(2j + 1)! 2 j=0 (9) where j ∈ {0, 1, · · · , n−1 }. Namely, 2 n−1 n−1 +j +j 2 2 a2j+1 = (−1) · (2j + 1)−1 · n · 22j . (10) 2j
n Tn (x) = 2
X
From the definition of w, one has n = ∓1 + h2w and w ≥ 2, n−1 where h ∈ Z. It means a1 = (−1) 2 n = 1 ∓ 2w h, where h w is an integer. Thus, 2 | (a1 − 1). Next, it follows from 2j+1 is odd and (10) that ν2 (a2j+1 ) ≥ 2j. The proof is divided into two cases depending on the value of j: 2j ≥ w: One has ν2 (a2j+1 ) ≥ 2j ≥ w, namely 2w | a2j+1 . 2 • 0 ≤ 2j < w: One can get ν2 (n − 1) = w + 1 ≥ 2(j + 1) from (8) and w is an integer. It yields from 2(j + 1) ≥ ν2 (2(j + 1)) that
•
ν2 (n2 − 1) ≥ ν2 (2(j + 1)). 2
2
(11)
2
n −(2j+1) 2j+3 Since a2j+1 = n −1−4j(j+1) , one has = − (2j+3)(2j+2) 2(j+1) ν2 (a2j+3 ) − ν2 (a2j+1 ) = min{ν2 (n2 − 1), ν2 (4j(j + 1))} − ν2 (2(j + 1)). Then, according to (11) and ν2 (4j(j + 1)) ≥ ν2 (2(j + 1)), one has a
ν2 (a2j+3 ) − ν2 (a2j+1 ) ≥ 0. n−1
Note that a3 = (−1) 2 +1 n(n+1)(n−1) , one has 3·2 ν2 (a3 ) ≥ w from (8). Thus, one can get ν2 (a2j+3 ) ≥ ν2 (a2j+1 ) ≥ ν2 (a3 ) ≥ w and 2w | ai .
IEEE TRANSACTIONS
4
Theorem 1. If a Chebyshev permutation polynomial with an initial value x0 ∈ Z2k satisfies ( Tn (x0 ) ≡ x0 (mod 2s ); (12) Tn (x0 ) ̸≡ x0 (mod 2s+1 ), then
k−s
Tn2
(mod 2k ),
(x0 ) ≡ x0
(13) k−s
and the least period of the sequence S2k (x0 ; n) is 2 k ≥ s and v ≥ 0.
, where
ν2
(j) Φ
(x0 ) (qm 2s+m )j j!
X f (j) (x) · hj , j! j=2
≥ 1 + (s + m)j − j + s2 (j) ≥ m+1
2(s+m) ≥ s+m+2. Thus, Φ(x0 +qm ·2s+m ) = Tn2 (x0 ) ≡ x0 + qm · 2s+m+1 (mod 2s+m+2 ). This means (15) remains valid for t = m + 1. To conclude, this result is applied to the specific case where t = k − s and t = k − s − 1. From the induction, one deduces ( k−s Tn2 (x0 ) ≡ x0 (mod 2k ), k−s Tn2 (x0 ) ̸≡ x0 (mod 2k+1 ), and
Proof. The Taylor expansion of a polynomial f (x) at a point x is given by deg(f )
( k−s−1 Tn2 (x0 ) ≡ x0 2k−s−1 Tn (x0 ) ̸≡ x0
(mod 2k−1 ), (mod 2k ).
(14)
Thus, the least period of the sequence S2k (x0 ; n) is 2k−s , and the least period of S2k+v (x0 ; n) is 2v times that of S2k (x0 ; n).
where deg(f ) denotes the degree of the polynomial f (x). Next, mathematical induction on t, one can prove ( t Tn2 (x0 ) ≡ x0 (mod 2s+t ); (15) t Tn2 (x0 ) ̸≡ x0 (mod 2s+t+1 ),
B. The Period Properties of Chebyshev Integer Sequence over Ring Z3k
′
f (x + h) = f (x) + h · f (x) +
where t is a non-negative integer. The base case of induction, t = 0, is directly given by the conditions in Eq. (12), which state that ( Tn (x0 ) ≡ x0 (mod 2s ), Tn (x0 ) ̸≡ x0 (mod 2s+1 ). Assuming that this pair of modular relations holds for t = m, namely ( m Tn2 (x0 ) ≡ x0 (mod 2s+m ), m Tn2 (x0 ) ̸≡ x0 (mod 2s+m+1 ), the goal is to demonstrate that (15) holds for t = m + 1. m Let Φ(x0 ) = Tn2 (x0 ). From the inductive hypothesis, it follows that Φ(x0 ) = x0 + qm · 2s+m , where qm is an odd integer. The next iteration of Tn , denoted m+1 Tn2 (x0 ), is given by m+1
Tn2
m
m
(x0 ) = Tn2 (Tn2 (x0 )) = Φ(Φ(x0 )) = Φ(x0 +qm ·2s+m ).
Now, the Taylor expansion (14) is applied with x = x0 and h = qm · 2s+m . Expanding Φ(x0 + qm · 2s+m ) yields Φ(x0 + qm · 2s+m ) = Φ(x0 ) + qm · 2s+m (Φ′ (x0 ) + 1) deg(Φ)
X Φ(j) (x0 ) (qm · 2s+m )j . j! j=2
+
The derivative of Φ(x0 ) is given by ′
Φ (x0 ) =
2m −1 Y
Tn′ (xi ),
i=0
and since Tn′ (xi ) ≡ 1 (mod 4), it follows that Φ′ (x0 ) ≡ 1
(mod 4).
Since Tn (x0 ) ≡ x0 (mod 4), it follows from (12) that s ≥ 2. Combining with the condition m ≥ 1, then
Lemma 3 provides an exact estimation of the power of 3 dividing the derivatives of Chebyshev polynomials at the endpoints. Additionally, Lemma 4 characterizes the congruence properties of the first derivative at the origin and evaluates their influence on the divisibility of higher-order derivatives. Finally, Theorem 2 establishes an explicit expression for the period distribution of Chebyshev sequences. Lemma 3. As for any Chebyshev polynomial Tn (x), one has ! (m) Tn (±1) · 3m ν3 ≥w+2 m! for any m ≥ 3. where w is a positive integer. Proof. The validity of the Lemma for 3 ≤ m ≤ 5 is verified through direct calculation using (7). Consequently, the subsequent proof concentrates on the case m ≥ 6. Referring to (7) and ν3 (n2 − 1) = w, one obtains (m) T (±1)·3m ν3 n m! ≥ w+ν3 (B)−ν3 ((2m−1)!!)+m−ν3 (m!), m−1 Q 2 2 where B = (n −j ). Note that ν3 (m!)+ν3 ((2m−1)!!) = j=2
ν3 (m) + ν3((2m − 1)!) from (2m − 1)!! = m·(2m−1)! 2m−1 ·m! . Thus,
one has ν3
Tn(m) (±1)·3m m!
≥ w+ν3 (B)−ν3 ((2m−1)!)+m−
ν3 (m). According to Legendre’s formula, ν3 (x!) = x−s23 (x) , one has ν3 ((2m − 1)!) = 2m−1−s23 (2m−1) . As s3 (x) ≥ 1 for x > 0, it further deduces ν3 ((2m − 1)!) ≤ m − 1. Hence, ! (m) Tn (±1) · 3m ν3 ≥ w + 1 + ν3 (B) − ν3 (m). (16) m! Let ν3 (m) = h, one has m = a3h , where a ≥ 1 and h ≥ 0. From n2 − 1 ≡ 0 (mod 3w ), one has n2 − j 2 ≡ 0 (mod 3) if j ≡ ±1 (mod 3). Thus, one gets 2m − 3 2 · a3h − 3 ⌋=⌊ ⌋. (17) 3 3 If h = 0, one has ⌊ 2m−3 m ≥ 3. If h = 1, 3 ⌋ ≥ h + 1 from h one has a ≥ 2 from m ≥ 6, and ⌊ 2·a33 −3 ⌋ = 2a − 1 ≥ h + 1. ν3 (B) = ⌊
IEEE TRANSACTIONS
5
If h > 1, one has the inequality 2a · 3h−1 − 1 ≥ h + 1. Thus, one can obtains ν3 (B) ≥ ν3 (m) + 1. Then, it further gets T (m) (±1)·3m ν3 n m! ≥ w + 2 for any m ≥ 6 from (16). Lemma 4. Let w = max{ν3 (n− 1), ν3 (n + 1)}, one has (m)
Tn′ l0 (0) ≡ 1 (mod 3w ) and ν3
T l (0)·3m n 0
m!
≥ w + 2 for
any m ≥ 2, where l0 = ord(Tn′ (0)). Proof. From the definition of w, one has n ≡ ±1 (mod 3w ). Note that the case n ≡ −1 (mod 3w ) is similar to n ≡ 1 (mod 3w ), only the latter case is considered in the following proof. Setting n = 1 + h · 3w , one has h mod 4 ∈w{0, 2} as n is h·3 odd. It yields from (3) that Tn′ (0) = (−1) 2 n. Next, one ′ w can prove Tnl0 (0) ≡ 1 (mod 3 ) depending on the value of h: ′ • h ≡ 0 (mod 4): One has Tn (0) = n, and n ≡ 1 w (mod 3) from n ≡ 1 (mod 3 ). So, l0 = ord(Tn′ (0)) = 1, which means Tn′ l0 (0) = n ≡ 1 (mod 3w ). ′ • h ≡ 2 (mod 4): One has Tn (0) = −n, and −n ≡ −1 (mod 3) from n ≡ 1 (mod 3w ). So, l0 = ord(Tn′ (0)) = n2 −1 2. So, Tn′ 2 (0) = (−1) 2 n2 = n2 . It yields from n ≡ 1 (mod 3w ) that Tn′ 2 (0) ≡ 1 (mod 3w ). Hence, Tn′ l0 (0) = n ≡ 1 (mod 3w ). It means nl0 ≡ 1 (mod 3w ) and n2l0 ≡ 1 (mod 3w ). Furthermore, from [13, (m−2) (m) Lemma 3], one has Tnl0 (0) = −(n2l0 −(m−2)2 )Tnl0 (0). (m) Then one can get ν3 (Tnl0 (0)) ≥ ν3 (n2l0 − 1) ≥ w for (m) m ≡ 1 (mod 2) and Tnl0 (0) = 0 for m ≡ 0 (mod 2). m (m) Hence, ν3 (T w. Combining with ν3 ( 3m! ) ≥ 2, one nl0 (0)) ≥ (m)
can get ν3
T l (0)·3m n 0
m!
≥ w + 2.
Theorem 2. Given s ∈ Zpk \{0, 1}, the least period of sequence S3k (s; n) is ls · 3k−vs when k ≥ vs , where ls = ord(Tn′ (s)) and vs = νp (Tnls (s) − s). Proof. First, based on the different values of s, it can be proven that vs ≥ 2. • s ≡ ±1 (mod 3): In this scenario, s can be expressed as s = 3h ± 1 for some integer h. Combining the definition of n yields ls = 1. Applying Taylor’s formula provides
Tnls (s) ≡ 3h · (1 + 3q) ≡ s (mod 32 ), establishing vs ≥ 2. Then, one can prove ( t Tn3ls (s) ≡ s (mod 3vs +t ); (18) t Tn3ls (s) ̸≡ s (mod 3vs +t+1 ) via mathematical induction on t. When t = 0, relation (18) holds. Assume that (18) holds e for t = e ≥ 0, namely Tn3ls (s) = s + qs · 3vs +e , where qs ̸≡ 0 (mod 3). e e+1 Let Φ(x) = Tnlx ·3 (x), then Tnlx 3 (x) = Φ3 (x) from the semi-group property of Chebyshev polynomial. By Taylor’s formula, Φ2 (s) = Φ(s + qs 3vs +e ) = Φ(s) + qs 3vs +e Φ′ (s) deg(Φ)
+
X Φ(j) (s)(qs 3vs +e )j . (19) j! j=2
(j)
Note that Φ j!(s) is an integer from Φ(x) is an integer coefficient polynomial, and (vs + e)j ≥ vs + e + 2 for j ≥ 2. It yields from (19) that Φ2 (s) ≡ s + qs (1 + Φ′ (s)) (mod 3vs +e+2 ). Following the same procedure as in (19), one can obtain Φ3 (s) = Φ(Φ2 (s)) ≡ s + qs 3vs +e (1 + Φ′ (s) + (Φ′ (s))2 )
(mod 3vs +e+2 ). (20) When s ≡ ±1 (mod 3), from (7), one has Tn′ ls 3e (s) ≡ e n2ls 3 (mod 3). Then one further gets Tn′ ls 3e (s) ≡ 1 (mod 3) from n2 ≡ 1 (mod 3).e When s ≡ 0 (mod 3), Tn′ ls 3e (s) ≡ Tn′ ls 3e (0) ≡ (−1) 1, (−1)
e n3 −1 2
e
n3 2
nls 3 −1 2
e
nls 3 (mod 3). If ls =
≡ 1 (mod 3) for n ≡ ±1e (mod 3). If n2·3 −1
e
ls = 2, from n ≡ 1 (mod 3), one has (−1) 2 n2·3 ≡ 1 (mod 3). Hence, Φ′ (s) ≡ 1 (mod 3). It means 1 + Φ′ (s) + (Φ′ (s))2 ≡ 3 (mod 9) in (20). Then, one can obtain Φ3 (s) ≡ s + qs 3vs +e+1 (mod 3vs +e+2 ) and (18) holds for t = e + 1. Finally, setting s = k − vs in (18), then one can get the least period of the sequence S3k (s; n) is ls · 3k−vs .
IV. T HE G RAPH S TRUCTURE OF C HEBYSHEV P ERMUTATION P OLYNOMIALS n (i) X Tn (±1)3i hi This Section analyzes the graph structure of Chebyshev Tn (±1+3·h) = Tn (±1)+Tn′ (±1)·3h+ . permutation polynomials over two distinct modular rings: i! i=2 Sec. IV-A examines Z2k via the parity of states, and Sec. IV-B Tn(i) (±1) It yields from is an integer that studies Z3k through the perspective of residue classes modulo i! (i) i i 3. Let G(Tn /Zpk ) denote the functional graph of the nT (±1)3 h ≥ 2. Thus, Tn (±1 + 3 · h) ≡ th order Chebyshev permutation polynomial over ring Z k , ν3 n i! p ±1 + 3hTn′ (±1) (mod 32 ). Furthermore, from and Cyc(L, •) as a cycle of length L in a graph. Then, Tn′ (±1) ≡ n2 ≡ 1 (mod 32 ), one has the expression k × Cyc(L, •) represents the configuration Tn (±1 + 3 · h) ≡ ±1 + 3h (mod 32 ). Based on of k distinct components, each possessing a cycle of length L the definition of vs , the inequality vs ≥ 2 is established. L. In addition, the direct operator denotes the disjoint • s ≡ 0 (mod 3): One can get s = 3h and ls ∈ {1, 2}. union of these heterogeneous topological structures within Analogous to the preceding case, applying Taylor’s for- the graph. For instance, as illustrated in Fig. 1 c), the graph L L mula, one has Tnls (3h) ≡ 3h · Tn′ ls (0) (mod 32 ). G(T19 /Z25 ) = 2i=1 2 × Cyc(2i , •) 20 × Cyc(1, •) signin−1 It yields from Tn′ (0) ≡ (−1) 2 n that Tn′ ls (0) = fies that the functional graph of the 19-th order Chebyshev (Tn′ (0))ls ≡ 1 (mod 3). The term Tn′ ls (0) can be polynomial over the ring Z25 is composed of 20 self-loops, expressed as 1 + 3q for some integer q. Therefore, two cycles of length two, and two cycles of length four.
IEEE TRANSACTIONS
6
A. The Graph Structure of Chebyshev Permutation Polynomials over Ring Z2k Chebyshev permutation polynomials over the ring Z2k exhibit significant algebraic regularities throughout the iteration process, where the induced functional graph admits a natural decomposition into independent components with distinct topological features based on the parity of the states. Building upon the inherent properties of these polynomials modulo 2k , Proposition 1 provides a rigorous characterization of the subgraphs constituted by odd states, specifying the exact distribution of cycle lengths and their respective multiplicities. Furthermore, Proposition 2 details the state-transition trajectories and cycle architectures that originate from even states. Proposition 1. As for any Chebyshev polynomial, all odd states consist of G(Tn /Z2k ) =
k−w−3 M
2w+1 × Cyc(2t , •) ⊕ 2w+2 × Cyc(1, •),
t=1
if k ≥ w + 3; G = 2k × Cyc(1, •) otherwise. Specially, the states of 2w+1 cycles Cyc(2t , •) are
Proof. For any odd state, it can be expressed as 1 + 2j, where j is an integer. By Taylor’s formula and Tn (1) = 1, one has n X (2j)m m=1
m!
· Tn(m) (1).
(21)
m
Note that ν2 ( 2m! ) = ν2 (2m ) − ν2 (m!) = s2 (m) ≥ 1 from Legendre’s formula. So, one has s2 (m) + ⌊ m 2 ⌋ ≥ 4 when (m) (2j)m m ≥ 5, yielding ν2 ( m! · Tn (1)) ≥ w + 4 from (6). It m P4 (m) yields from (21) that Tn (1 + 2j) ≡ 1 + m=1 (2j) m! Tn (1) w+4 (mod 2 ). By incorporating (7) into the previous congru2 2 ence Tn (1 + 2j) ≡ 1 + 2jn2 + 2j 2 n (n3 −1) + (j 3 + j 4 )2w+3 (mod 2w+4 ) ≡ 1 + 2j + 2(n2 − 1)(j + 3−1 n2 j 2 ) (mod 2w+4 ) Note that n2 ≡ 1 (mod 2w+1 ) from (8) and 3−1 ≡ 3 (mod 4), one obtains Tn (1 + 2j) ≡ 1 + 2j + j(1 + 3j)2w+2
2w+1 × Cyc(2t , •) ⊕ 2w+2 × Cyc(1, •).
t=1
where 2w+2 self-loop cycles are {1 + 2s−1 j, 2s−1 − 1 + 2s−1 | j ∈ Aw+1 }, which yields that Tn (1+2s−1 j) ≡ 1+2s−1 j mod 2w+s and Tn (2s−1 −1+2s−1 j) ≡ 2s−1 −1+2s−1 j mod 2w+s . From Lemma 1, one can get Tn (1 + 2s−1 j) ≡ Tn (1) + 2s−1 j · Tn′ (1) ≡ 1 + 2s−1 j + 2w+s j ( 1 + 2s−1 j (mod 2w+s+1 ) if j ≡ 0 mod 2; ≡ s−1 w+s w+s+1 1+2 j+2 (mod 2 ) if j ≡ 1 mod 2, and ≡ Tn (−1) + 2s−1 (j + 1) · Tn′ (1)
w+2
where j1 ∈ Aw and At = {0, 1, · · · , 2 − 1} and 2 selfloops are {1 + 2k−w−1 j, (j + 1)2k−w−1 − 1|j ∈ Aw+1 }.
Tn (1 + 2j) = 1 +
G(Tn /Z2w+s ) =
s−3 M
Tn (−1 + 2s−1 + 2s−1 j)
{2k−w−t−1 ± 1 + 2k−w−t j1 + 2k−t j2 |j2 ∈ At }, t
remain self-loop, and half of the states with j mod 4 ∈ {2, 3} have their period changed in graph G(Tn /Z2w+4 ). Thus, this proposition holds for k = w + 4. Assume this proposition is true for k = w + s with s ≥ 4, namely
(mod 2w+4 ). (22)
≡ −1 + 2s−1 (j + 1) + 2w+s (j + 1)
(mod 2)w+s+1
where j ∈ Aw+1 . Accordingly, depending on the parity of j, one obtains Tn (−1 + 2s−1 + 2s−1 j) ≡ −1 + 2s−1 + 2s−1 j (mod 2w+s+1 ) when j ≡ 1 (mod 2), and Tn (−1 + 2s−1 + 2s−1 j) ≡ −1+2s−1 +2s−1 j+2w+s (mod 2w+s+1 ) when j ≡ 0 (mod 2). Hence, Tn (1+2s j) ≡ Tn (1+2s−1 j ++2s−1 j) ≡ 1 + 2s j mod 2w+s+1 and Tn (−1 + 2s + 2s j) ≡ Tn (−1 + 2s−1 + 2s−1 j + 2s−1 + 2s−1 j) ≡ −1 + 2s + 2s j mod 2w+s+1 . and Tn2 (1 + 2s (2j1 + 1)) ≡ Tn (1 + 2s (2j1 + 1) + 2w+s ) ≡ 1 + 2s (2j1 + 1) mod 2w+s+1 with j1 ∈ Aw , those are 2w cycles with Cyc(2, •) = {1 + 2s−1 + 2s j1 + 2w+s j2 |j2 ∈ A1 }. Similarly, one has Tn2 (−1 + 2s−1 + 2s j1 )) ≡ Tn (−1 + 2s−1 + 2s j1 + 2w+s ) ≡ −1 + 2s−1 + 2s j1 mod 2w+s+1 , those are 2w cycles Cyc(2, •) = {−1 + 2s−1 + 2s j1 + 2w+s j2 |j2 ∈ A1 }. Referring to [21, Theorem 2], one can know cycle Cyc(2t−1 , •) = {2s−t ±1+2s−t+1 j1 +2w+s−t+1 j2 |j2 ∈ At−1 }, in G(Tn /Z2w+s ) changes cycle Cyc(2t , •) = {2s−t ± 1 + 2s+1−t j1 + 2w+s+1−t j2 |j2 ∈ At }
Hence, Tn (1 + 2j) ≡ 1 + 2j + (j + j 2 )2w+2 ≡ 1 + 2j
(mod 2w+3 )
(mod 2w+3 ).
Consequently, when k ≤ w + 3, every odd state corresponds to a self-loop, and thus the graph can be represented as G = 2k × Cyc(1, •). This result verifies that the proposition holds for all k ≤ w + 3. When k = w + 4, referring to (22), one can get ( 1 + 2j if j mod 4 ∈ {0, 1}; Tn (1 + 2j) ≡ 1 + 2j + 2w+3 if j mod 4 ∈ {2, 3}. This means that for all self-loop states {1 + 2j | j ∈ Aw+2 } in G(Tn /Z2w+3 ), half of the states with j mod 4 ∈ {0, 1}
in G(Tn /Z2w+s+1 ) as the precision k increases by one. Therefore, this Property also holds for k = w + s + 1. Proposition 2. As for any Chebyshev polynomial, all even states consist of G(Tn /Z2k ) =
k−w−1 M
2w−1 × Cyc(2t , •) ⊕ 2w × Cyc(1, •),
t=1
if k > w + 1; G(Tn /Z2k ) = 2k × Cyc(1, •) otherwise. Specifically, the 2w−1 Cyc(2t , •) are generated from initial values x0 in the set {2k−w−t (2j1 + 1) + 2k−t j2 | j2 ∈ At },
IEEE TRANSACTIONS
7
where j1 ∈ Aw−1 and Ai = {0, 1, · · · , 2i − 1}. Moreover, the 2w self-loops are generated from initial values x0 in the set {2k−w j | j ∈ Aw }. Proof. Note that Tn (2j) = a1 · 2j + a3 (2j)3 + · · · + an (2j)n . It yields from Lemma 2 that Tn (2j) ≡ 2j mod 2w+1
(23)
Figure 1 illustrates the evolution of the functional graph of the Chebyshev polynomial of degree 19 over the ring Z2k as k continuously increases. Combining Propositions 1 and 2, it can be calculated that w = 2, then one has all odd states consist of G(Tn /Z27 ) =
8 × Cyc(2t , •)
M
16 × Cyc(1, •);
t=1
w
for all j ∈ {0, 1, · · · , 2 − 1}. Thus, all even states form selfloops when k ≤ w + 1, which is represented as G(Tn /Z2k ) = 2k × Cyc(1, •). When k = w + 2, for any j ∈ Aw+1 , Lemma 2 implies Tn (2j) ≡ 2j(2w ±1+h·2w+1 ) mod 2w+2 ≡ 2j +2w+1 j mod 2w+2 . Hence, ( 2j mod 2w+2 when j ≡ 0 mod 2; Tn (2j) ≡ 2j + 2w+1 mod 2w+2 when j ≡ 1 mod 2.
2 M
all even states consist of G(Tn /Z27 ) =
4 M
2 × Cyc(2t , •)
M
Therefore, one obtains the functional graph G(Tn /Z27 ) =
4 M
2 × Cyc(2t , •)
t=3
Applying Tn once again yields
2 M
10 × Cyc(2t , •)
t=1
M
Tn2 (2j) ≡ ( Tn (2j) (mod 2w+2 ) when j ≡ 0 w+1 w+2 Tn (2j + 2 ) (mod 2 ) when j ≡ 1
(mod 2); (mod 2).
In both cases, Tn2 (2j) ≡ 2j (mod 2w+2 ). The two congruences above imply that all states of the form x = 2j are self-loops, where j ∈ Aw+1 and j ≡ 0 (mod 2), they form 2w self-loops, that is 2w × Cyc(1, •). Meanwhile, all states w+1 w of the form x = 2j constitute 2 2−2 = 2w−1 cycles of length 2, where j ∈ Aw+1 and j ≡ 1 (mod 2), expressed as 2w−1 × Cyc(2, •). This confirms that the proposition holds for k = w + 2. Assume the Proposition holds for any k = w + s, namely G(Tn /Z2w+s ) =
s−1 M
2w−1 × Cyc(2t , •) ⊕ 2w × Cyc(1, •),
t=1
where 2w self-loop cycles are {2s j|j ∈ Aw }, which yields that Tn (2s j) ≡ 2s j mod 2w+s . Similar to (23), one has Tn (2s j) ≡ 2s j(2w ± 1 + h · 2w+1 ) mod 2w+s+1 s
w+s
w+s+1
≡2 j+2 j mod 2 ( 2s j mod 2w+s+1 ≡ 2s j + 2w+s mod 2w+s+1
if j ≡ 0 mod 2; if j ≡ 1 mod 2.
It further follows from the above equation that Tn2 (2s j) ≡ 2s j
(mod 2w+s+1 ).
This implies that the states x ∈ {2, 4, 6, . . . , 2w − 2} are selfloops, while the states x ∈ {1, 3, 5, . . . , 2w − 1} form cycles of length two. Referring to [21, Theorem 2], we know that the cycle Cyc(2t−1 , •) = {2s−t+1 j1 + 2w+s−t+1 j2 | j1 , j2 ∈ At } in G(Tn /Z2w+s ) transforms into the cycle t
s+1−t
Cyc(2 , •) = {2
4 × Cyc(1, •).
t=1
j1 + 2
w+s+1−t
j2 | j1 , j2 ∈ At }
in G(Tn /Z2w+s+1 ) as the precision k increases by one, where j1 ≡ 1 (mod 2), j2 ≡ 0 (mod 2). Therefore, this property also holds for k = w + s + 1.
20 × Cyc(1, •),
The structure exhibited in Figure 1 e) is consistent with the deduced structure. Corollary 1. Let L(n, 2, k, x) denote the period of the n-th order Chebyshev permutation polynomial at x ∈ Z2k . Then ′ k −ν2 (x) when x ≡ 0 (mod 2), k ′ > 1, 2
L(n, 2, k, x) =
′
∗
2k −ν2 (x)−1
1
when x ≡ 1 (mod 2), k ′ > 3,
otherwise,
where k ′ = k − ν2∗ (n), ν2 (x) denotes the 2-adic valuation of x, and ν2∗ (x) = max{ν2 (x − 1), ν2 (x + 1)}. Proof. Based on the functional graph structure Propositions 1 and 2 concerning odd and even states, we can derive the result of this corollary. B. The Graph Structure of Chebyshev Permutation Polynomials over Ring Z3k Based on the distribution of initial states among modulo 3 residue classes, as described in Theorem 2, the evolution paths and dynamical characteristics of various vertices within the functional graph are thoroughly examined in this section. Proposition 3 further precisely locates the distribution of self-loops within the functional graph. Combining the period distribution with the topological features of self-loops, Proposition 4 comprehensively characterizes the functional graph for the case x ≡ 0, detailing the lengths and corresponding cycles. Analogously, Proposition 5 details the functional graph for the case of x ≡ ±1. Due to the methodological similarity in the derivations, the proof of Proposition 5 is omitted. Proposition 3. Let Rk be the set of values of self-loops in G3k whose values belong to A1 . Then, one has Rk = A1 if k ≤ w + 1; otherwise Rk = {x ∈ A1 | x ≡ (±1 +
k−w−1 X i=1
ji 3i )
(mod 3k−w ), }
IEEE TRANSACTIONS
8
14
10
12
4
30
22 26
18
12
28
4
20
6
2
8
0
6
14
2
10
24
8
16
0
6
2
7
5
15
7
13
5
31
15
23
7
29
13
21
5
4
0
3
1
11
3
9
1
27
11
19
3
25
9
17
1
a) 46
6
b) 2
54
62
58
42
30 18
22
38
44
10
52
60 56
54 110 6
28
36
40
20 48 32
12
50
c)
34
24
8
16
0
63
47
55
39
61
45
53
37
31
15
23
7
29
13
21
5
59
43
51
35
57
41
49
33
27
11
19
3
25
9
17
1
126
102
66
86
12
34
58
74
14 82
18
22
38
122
62
10
30
98
70 46 118
2 90 114 42
127 63
111 47
119
55 103
39
95
79
87
23
7
31
15
75 27 59 123 107 43 11 91
71
28
84
108
60
78
26
14
106 50 26
94
4
100
52
76
92
116
36
124
44
68
20
4
88 112 48 96 32 72 56 120 104 40 24 8 80 16 64 0
61
5 29 77 21 125 45 109 53 117 37 101 69 93 13 85
121 57 105 83 3 51 115 35 99 89 25 73 19 67
41 9
113 49
97 33
81
65
17
1
e) d) Fig. 1: Functional graphs of Chebyshev polynomial (n, p) = (19, 2): a) e = 3; b) e = 4; c) e = 5; d) e = 6; c) e = 7. 174 123 66 15
43
223 196
16
169
232
34
97 124
178
61
151
157
85
139
238 76
58 220
49 8
170
211
212
52 64
140
59
184 131
79
221 127
208
50 130
155
241 25
46
4
166
89
115 88
35
103
197 116
101 118
179 17 98
185
22
173
199
31
193 112
86 239
77
181
23 104
158
233
44
235 71
30
93 213
105
152
154
42
109
94
190
95
67
202
68
161
203
82
163
229
230
53
148
149
55
40
26
136
41
1
80
121
215
242
13
122
14
28
107
217
175
188
134
72
36
126
183 33
237
6
222
210
48 60
168 156 114 102
198
9 45
234
21
62
176
132 192 159 219
90
195
143
3
186
141 129 87 75
224
172
228 177 120 69
194
10
165
204 12
113
91 73
78
147
218 32
206
57
240
96 138
191
2
125 5
167
19
100
119
51
150
29 92
146
37
164
84
111
201
56 65
74
128
226
145
137
200 47
106
39
110
83 38
182
214 142
205
11
227
20
133
7
70
209 236
187 160
24 231
171 225
153 180 144
99 63
117 81
207 27
108
54
162 135 216 189
18
0
a) b) Fig. 2: Functional graphs of Chebyshev polynomial (n, p, k) = (19, 3, 5) with all status satisfying: a) x ≡ 0 (mod 3) b) x ≡ ±1 (mod 3). where A1 = {x|x ∈ Zk , x ≡ ±1 (mod 3)}, (
to (7), one has
{0, 1} {−qi (1 + j1 )−1 mod 3}
when i = 1, ji ∈ when 2 ≤ i ≤ k − w − 1, (24) Pi−1 t Pi−1 t T (±1+ t=1 3 jt )∓1+ t=1 3 jt and qi = n . 3w+i Proof. Since x ≡ ±1 (mod 3) and x ∈ Z3k , one can set x = Pk−1 (±1 + 3h) mod 3k , where h = i=1 ji 3i−1 , ji ∈ {0, 1, 2} for 1 ≤ i ≤ k − 1. Applying Taylor’s formula, one obtains (3h)n (n) Tn (±1+3h) = ±1+3hTn′ (±1)+· · ·+ Tn (±1). n!
m
(m)
(25)
w+2 From Lemma 3, one has (3h) ) m! · Tn (±1) ≡ 0 (mod 3 for any m ≥ 3. It yields from (25) that Tn (±1 + 3h) ≡ h2 32 Tn′′ (±1) ±1 + 3hTn′ (±1) + (mod 3w+2 ). Then, according 2
Tn (±1+3h) ≡ ±1+3h+3h(n2 −1)(1+2−1 an2 )
(mod 3w+2 ). (26) Note that t ≡ j1 (mod 3) and (1 + 2−1 hn2 ) ≡ (1 + 2j1 ) (mod 3). Substituting the two congruences and ν3 (n2 − 1) = w into (26), one gets ( ±1 + 3h + 3w+1 · j1 (1 + 2j1 ) (mod 3w+2 ); Tn (±1+3h) ≡ ±1 + 3h (mod 3w+1 ). Thus, Rk = A1 when k ≤ w+1, and Rw+2 = {x ∈ Z3k | x ≡ ±1 + 3j1 (mod 9)}, where j1 ∈ {0, 1}. Suppose the proposition holds forP k = w + s with s ≥ 2, Ps−1 s−1 one has Tn (±1+ i=1 ji 3i ) ≡ ±1+ i=1 ji 3i (mod 3w+s ), Ps−1 i where ji satisfies (24). Denote ∆ = i=1 3 ji , one has Tn (±1 + ∆) = ±1 + ∆ + qs · 3w+s .
(27)
IEEE TRANSACTIONS
9
When k = w + s + 1, applying Taylor’s formula obtains Tn (±1 + ∆ + 3s Bs ) = n X (3s Bs )m (m) Tn (±1 + ∆) + Tn (±1 + ∆), (28) m! m=1 T (m) (±1+∆)·3m i−s = . Note that n i=s ji 3 m! Pn Tn(m) (±1)·3m ∆i−m ·Tn(i) (±1)·3m Tn(m) (±1)·3m + i=m+1 = + m! (i−m)!·m! m! i (i) Pn ∆ i−m i Tn (±1)·3 . It yields from Lemma 3 that i=m+1 ( 3 ) m i!
where Bs =
Pk
(m)
(±1 + ∆) · 3m ≡ m! w+2 ) if m ≥ 3; 0 ′′ (mod 3 2 Tn (±1)·3 w+2 (mod 3 ) if m = 2; ′2 ′′ w+2 3Tn (±1) + 3∆Tn (±1) (mod 3 ) if m = 1. Tn
s
m
k ≤ w + 1: From Lemma 4 and (30), one obtains Tn (3t) ≡ 3t · Tn′ (0) (mod 3k ). It means Tn (x) ≡ x · Tn′ (0) (mod 3k ). Hence, Tni (x) = Tn (Tni−1 (x)) ≡ x·[Tn′ (0)]i (mod 3k ). From Lemma 4, one has Tn′ l0 (0) = [Tn′ (0)]l0 ≡ 1 (mod 3)k , which further gets Tnl0 (x) ≡ x (mod 3k ). Therefor, from the definition of l0 , one can get l0 is the least integer such Tnl0 (x) ≡ x (mod 3k ). k−1 Hence, there are 3 l0 −1 cycles of length l0 in G3k . • k ≥ w + 2: If ν3 (t) ≥ k − w − 1, i.e. k ≤ ν3 (t) + w + 1, it yields from (30) that Tn (3t) ≡ 3t · Tn′ (0) (mod 3k ). w Then from the above case, one obtains there are 3 l0−1 cycles of length l0 in G3k . If ν3 (t) ≤ k − w − 2, one has vs = w + 1 + ν3 (t) in Theorem 2. Then, the least period of the sequence is l0 3k−w−1−ν3 (t) . Let s = ν3 (t), one obtains the number of cycles of length l0 3i is •
(29)
2 · 3k−2−s 2 · 3w−1 |{t ∈ Z3k−1 | ν3 (t) = s}| = = , k−w−1−s k−w−1−s l0 3 l0 3 l0
(m)
Bs ) Tn (±1 + ∆) ≡ 0 (mod 3w+s+1 ) for any m ≥ So, (3 m! s (3 Bs )2 Tn′′ (±1+∆) (3s Bs )2 ·Tn′′ (±1) 3, ≡ (mod 3w+s+1 ), and 2 2 s ′′ s ′ s ′ 3 Bs Tn (±1+∆) ≡ 3 Tn (±1)+3 ∆Tn (±1) (mod 3w+s+1 ). Substituting the previous three congruences into (28), one gets Tn (±1 + ∆ + 3s Bs ) ≡ Tn (±1 + ∆) + 3s Bs (Tn′ (±1) + (3s Bs )2 ·Tn′′ (±1) ∆Tn′′ (±1)) + (mod 3w+s+1 ). It yields from 2 s (7) that Tn (±1 + ∆ + 3 Bs ) ≡ Tn (±1 + ∆) + 3s Bs n2 + 2 3s−1 ∆Bs n2 (n2 −1)+32s−1 Bs2 n(n2−1) (mod 3w+s+1 ). Then, combining ν3 (n2 − 1) = w, one further gets Tn (±1 + ∆ + 3s Bs ) ≡ Tn (±1 + ∆) + 3s Bs + 3w+s (js + js j1 ) (mod 3w+s+1 ). Combining (27), one can get
Tn (±1 + ∆ + 3s Bs ) ≡ ±1 + ∆ + 3s Bs + 3w+s (qs + js + js j1 )
(mod 3w+s+1 ).
So, when (qs +js +js j1 ) ≡ 0 (mod 3), namely js = −qs (1+ j1 )−1 mod 3, one has Tn (±1 + ∆ + 3s Bs ) ≡ ±1 + ∆ + 3s Bs
Proposition 4. The connected components of G3k to which all states x satisfying x ≡ 0 (mod 3) belong, are composed w w−1 of 2·3l0 cycles of length l0 3i , 3 l0−1 cycles of length l0 , and k−1 one self-loop when k ≥ w + 2; 3 l0 −1 cycles of length l0 and one self-loops otherwise, where l0 = ord(Tn′ (0)), i ∈ {1, 2, · · · , k − w − 1}. Proof. When x = 0, one has Tn (0) = 0, which means the node with status value 0 is a self-loop in G3k . When x ≡ 0 (mod 3) and x ̸= 0, one can write x = 3t, where t is a positive integer. By Taylor’s formula, one has n (m) X (3t)m · Tn (0) m=2
Proposition 5. The connected components of G3k to which all states x satisfying x ≡ ±1 (mod 3) belong, are composed of 8·3w−1 cycles of length 3i , 4·3w self-loops, and 2·3w−1 cycles of length 3k−w−1 when k ≥ w + 2; and 2 · 3k−1 self-loops otherwise, where i ∈ {1, 2, · · · , k − w − 2}. As a typical example with n = 19, it is determined that w = 2 and l0 = 2. According to Propositions 4 and 5, all states x ≡L±1 (mod 3) form L the graph G(Tn /Z35 ) = 24 × cyc(3, •) 36 × cyc(1, •) 6 × cyc(9, •), whereas all states x ≡ 0L (mod 3) constitute L2 the graph G(Tn /Z35 ) = 1 × cyc(1, •) 4 × cyc(2, •) i=1 3 × cyc(2 · 3i , •). The functional graph structures illustrated in Fig. 2 a) and b) demonstrate complete consistency with Propositions 5 and 4, respectively.
(mod 3w+s+1 )
for when i ≥ s + 1. So, when x ≡ (±1 + Ps any jii ∈ {0, 1, 2} s+1 j 3 ) (mod 3 ), one has Tn (x) ≡ x (mod 3w+s+1 ), i i=1 which means the proposition holds for k = w + s + 1.
Tn (0 + 3t) = Tn (0) + 3tTn′ (0) +
where i = k − w − 1 − s ∈ {1, 2, . . . , k − w − 1}.
m!
. (30)
According to the value of k, the proof can be divided into the following two cases:
V. C ONCLUSION This paper analyzed the functional graph induced by Chebyshev permutation polynomials over the composite ring Z2k1 3k2 . By leveraging new structural properties of Chebyshev polynomials modulo powers of 2 and 3, we established explicit characterizations of both the path lengths and the cycle structures of the resulting dynamical systems. Despite the domain’s mixed binary-ternary nature, our results reveal that the functional graphs exhibit strong and predictable regularities. In particular, the number of fixed-length cycles remains constant under parameter scaling, and the associated branching patterns evolve in a controlled and analyzable manner as k1 and k2 increase. These findings extend existing studies on Chebyshev dynamics over prime-power rings to the broader setting of composite rings. Beyond their intrinsic number-theoretic interest, the results also shed light on how complexity emerges in digital nonlinear maps, thereby providing helpful theoretical support for evaluating the pseudo-randomness and security properties of Chebyshev-based constructions in cryptographic applications.
IEEE TRANSACTIONS
10
R EFERENCES [1] 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. [2] 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. [3] Q. Wang, S. Yu, C. Li, J. Lü, X. Fang, C. Guyeux, and J. M. Bahi, “Theoretical design and FPGA-based implementation of higherdimensional digital chaotic systems,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 63, no. 3, pp. 401–412, 2016. [4] 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. [5] F. Chen, K.-W. Wong, X. Liao, and T. Xiang, “Period distribution of the generalized discrete Arnold Cat map for n = 2e ,” IEEE Transactions on Information Theory, vol. 59, no. 5, pp. 3249–3255, 2013. [6] 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. [7] 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. [8] 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. [9] D. E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd ed. Reading, Massachusetts: Addison-Wesley Professional, 1997. [10] 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. [11] 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. [12] 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. [13] C. Li, X. Lu, K. Tan, and G. Chen, “The graph structure of Chebyshev permutation polynomials over ring Zpk ,” IEEE Transactions on Information Theory, vol. 71, no. 2, pp. 1419–1433, 2025. [14] C. Qureshi and D. Panario, “The graph structure of Chebyshev polynomials over finite fields and applications,” Designs, Codes and Cryptography, vol. 87, pp. 393–416, 2019. [15] 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. [16] D. Yoshioka, “Security of public-key cryptosystems based on Chebyshev polynomials over Z/pk Z,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 67, no. 10, pp. 2204–2208, 2020. [17] C. Panraksa and A. Tangboonduangjit, “Fixed-point lifting and ghost periodic points for chebyshev polynomials modulo odd prime powers,” 2026. [18] D. Yoshioka and K. Kawano, “Periodic properties of chebyshev polynomial sequences over the residue ring Z/2k Z,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 63, no. 8, pp. 778–782, 2016. [19] 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. [20] K. Umeno, “Key exchange by Chebyshev polynomials modulo 2w ,” in Proceedings of Indonesia Cryptology and Information Security, 2005, pp. 95–97. [21] D. Yoshioka and Y. Dainobu, “On some properties of Chebyshev polynomial sequences modulo 2k ,” Nonlinear Theory and Its Applications, vol. 6, no. 3, pp. 443–452, 2015.