betaFeedback

WorksMathematics

How random are affine maps over finite cyclic groups and generalized cyclotomic permutations over finite fields?

Abstract

We analyze the dynamical behavior of affine permutations over the ring Zpe\mathbb{Z}_{p^e} and generalized cyclotomic permutations (GCPs) over the finite field Fq\mathbb{F}_q. We use the description of their functional graphs to determine two statistical parameters: the expected number of cycles and the expected length of a cycle that contains a random element. We obtain explicit closed-form expressions for both expectations and an exact reduction from GCPs to affine permutations. We compare these parameters with the corresponding expectations for random permutations, to determine how closely the cycle statistics of each family resemble those of random permutations.

Introduction

A discrete dynamical system is a pair (S,f)(S,f), where the state space SS is a finite set and ff is a self map of SS. The iteration of the function ff determines the evolution of each state of the state space SS in a discrete time [10]. Associated with the discrete dynamical system (S,f)(S,f) is a directed graph Gf(S)\mathcal{G}_f(S), known as the functional graph of ff over SS, with vertex set V=SV=S and directed edges E={(x,f(x))∣x∈S}E=\{(x,f(x))\mid x\in S\}. This digraph is a visual representation of the evolution of each state of SS under the function ff.

Flajolet and Odlyzko [6] determined the asymptotic behavior of the functional graph associated with the discrete dynamical system (S,f)(S,f), where ff is a function selected uniformly at random. They obtain stochastic parameters, such as the expectation for cycle length, number of connected components and number of cycles of a given length for a function taken with uniform probability from the set SSS^{S} of all self maps of SS. The same statistical properties for random permutations can be found in [19]. Therefore, obtaining such parameters for a smaller set of functions is a natural way to compare their dynamical behavior to those of a truly random function. Many function families over finite structures have been investigated in that sense [11, 15, 16, 17].

The case where the state space SS is a finite field is particularly important due to its diverse applications in areas such as cybersecurity [3, 14], pseudorandom number generation [5, 13, 20, 22] and biology [1, 7]. Within this setting, dynamical systems induced by permutations are often sought out for being building blocks in cryptographic protocols. In this case, the functional graph consists exclusively of disjoint cycles, so that its dynamical behavior is completely determined by its cycle structure. Consequently, the number and lengths of cycles provide natural parameters for studying and comparing families of permutations over finite fields.

In this paper, we investigate stochastic properties of the functional graphs of two families of permutations: affine permutations over the finite cyclic group of order pep^{e} and generalized cyclotomic permutations over finite fields. Introduced by Niederreiter and Winterhof [12] and Wang [21], generalized cyclotomic mappings (or GCMs) of index dd are a generalization of monomial maps. Let qq be a prime power and dd a divisor of q−1q-1. An index dd GCM of the finite field Fq\mathbb{F}_{q} is any function f:Fq→Fqf:\mathbb{F}_{q}\to\mathbb{F}_{q} that satisfies f(0)=0f(0)=0 and agrees with a monomial function when restricted to each of the dd cosets of the unique index dd subgroup of Fq∗\mathbb{F}_{q}^{*}. A generalized cyclotomic permutation (or GCP) is a bijective GCM. The functional graphs of index dd GCMs are described by Bors, Panario and Wang in [2].

Clearly, any monomial permutation over Fq\mathbb{F}_{q} is an index 1 GCP. Their functional graph, described in [4], is highly dependent on the divisors of q−1q-1. However, any permutation of Fq\mathbb{F}_{q} that fixes 0 is a GCP of index q−1q-1. Thus, a randomly selected GCP is essentially a random permutation of Fq∗\mathbb{F}_{q}^{*}. A natural question is how the cycle statistics of GCPs change as the index increases, and how far from q−1q-1 the index can be while maintaining cycle statistics comparable to those of uniformly random permutations.

We obtain a group isomorphism through discrete logarithm between the index dd subgroup of Fq∗\mathbb{F}_{q}^{*} and the additive group Zs\mathbb{Z}_{s}, where s=q−1ds=\frac{q-1}{d}. We then obtain the expected number of cycles and the expected length of the cycle that contains a random element in the functional graph of a randomly selected generalized cyclotomic permutation in terms of the same expectations for affine permutations over Zs\mathbb{Z}_s.

Moreover, we determine explicit closed formulas for these expectations in affine permutations over Zpe\mathbb{Z}_{p^e}, where pp is a prime and ee is a positive integer. When pep^e divides q−1q-1, we consider index d=q−1ped=\frac{q-1}{p^e} GCPs. The exponent ee provides a natural parameter for controlling the size of dd, and consequently its distance from the maximal possible index q−1q-1. We derive the expectations for GCPs of this particular index and observe their asymptotics as ee grows. Finally, we provide a comparison between these expectations with the corresponding expectations for uniformly random permutations over a set of the same size.

We end this section by providing the structure of the paper. In Section 3, we describe the dynamical behavior of GCMs, determined by Bors, Panario and Wang in [2]. In Section 4, we derive a formula for the two statistical properties of index dd GCPs in terms of the corresponding properties for affine permutations over Zs\mathbb{Z}_s. In Section 5, we present Deng’s [4] characterization of functional graphs of affine maps over the finite cyclic group Zs\mathbb{Z}_s. Using this characterization, in Section 6 we derive the stochastic parameters for affine permutations over Zpe\mathbb{Z}_{p^e}. In Section 7, we provide a comparison between the properties from affine permutations over Zpe\mathbb{Z}_{p^e} and GCPs against the corresponding expectations for random permutations. In Section 8, we conclude the paper by summarizing our findings and presenting problems for future research.

Preliminary properties

In this section we present a list of lemmas needed in the proofs of our main results.

Throughout the paper, pp is a prime, [a,b][a,b] is the set of nonnegative integers greater or equal to aa and smaller or equal to bb, Zn\mathbb{Z}_n is the finite additive group of integers modulo nn and ord⁡n(a)\operatorname{ord}_n(a) is the smallest positive integer kk such that ak≡1(modn)a^k \equiv1 \pmod{n}, for aa coprime with nn. Moreover, we define νp(a)\nu_p(a) as the greatest k∈Zk \in\mathbb{Z} such that pkp^k divides aa and set νp(0)=∞\nu_p(0)=\infty.

Lemma 2.1 (Lifting The Exponent Lemma [9]). Let xx and nn be integers, and pp be a prime.

  1. If pp is an odd prime and νp(x−1)>0\nu_p(x-1)>0, then νp(xn−1)−νp(x−1)=νp(n)\nu_p(x^n-1)-\nu_p(x-1)=\nu_p(n).

  2. If p=2p=2 and nn is odd, then νp(xn−1)−νp(x−1)=νp(n)=0\nu_p(x^n-1)-\nu_p(x-1)=\nu_p(n)=0.

  1. If p=2p=2, nn is even and x≡1(mod4)x\equiv1 \pmod{4}, then νp(xn−1)−νp(x−1)=νp(n)\nu_p(x^n-1)-\nu_p(x-1)=\nu_p(n).

  1. If p=2p=2, nn is even and x≡3(mod4)x\equiv3 \pmod{4}, then νp(xn−1)−νp(x−1)=νp(x+12)+νp(n)\nu_p(x^n-1)-\nu_p(x-1)=\nu_p\left(\frac{x+1}{2}\right)+\nu_p(n).

Lemma 2.2. Let pp be a prime, jj a nonnegative integer, kk a positive integer and i∈[1,p−1]i\in[1,p-1]. If pp is odd, d=ord⁡p(i)d=\operatorname{ord}_p(i) and t=νp((jp+i)d−1)t=\nu_p((jp+i)^d-1), then ord⁡pk(jp+i)=d⋅pmax⁡{0,k−t}\operatorname{ord}_{p^k}(jp+i)=d\cdot p^{\max\{0,k-t\}}.

If p=2p=2, then ord⁡2k(4j+1)=2max⁡{0,k−2−ν2(j)}\operatorname{ord}_{2^k}(4j+1)=2^{\max\{0,k-2-\nu_2(j)\}}. Moreover, ord⁡2(4j+3)=1\operatorname{ord}_2(4j+3)=1 and, for all k>1k>1, ord⁡2k(4j+3)=2max⁡{1,k−2−ν2(j+1)}\operatorname{ord}_{2^k}(4j+3)=2^{\max\{1,k-2-\nu_2(j+1)\}}.

Proof. Let pp be an odd prime. For k=1k=1, we have that jp+i≡i(modp)jp+i\equiv i\pmod{p}, thus ord⁡p(jp+i)=ord⁡p(i)=d\operatorname{ord}_p(jp+i)=\operatorname{ord}_p(i)=d. Moreover, since pp divides pkp^k we have that ord⁡pk(jp+i)=d⋅r\operatorname{ord}_{p^k}(jp+i)=d\cdot r, for some positive integer rr. Hence, by Lemma 2.1, if k>1k>1 we have that

νp((jp+i)ord⁡pk(jp+i)−1)=νp((jp+i)d⋅r−1)=νp((jp+i)d−1)+νp(r)≥k.\nu_p\left((jp+i)^{\operatorname{ord}_{p^k}(jp+i)}-1\right)=\nu_p\left((jp+i)^{d\cdot r}-1\right)=\nu_p\left((jp+i)^d-1\right)+\nu_p(r)\geq k.

This implies that rr is the minimal positive integer that satisfies νp(r)≥k−t\nu_p(r)\geq k-t. Hence r=pmax⁡{0,k−t}r=p^{\max\{0,k-t\}}.

For p=2p=2, from Lemma 2.1, we have that ord⁡2k(4j+1)\operatorname{ord}_{2^k}(4j+1) is the minimal nonnegative integer rr that satisfies

ν2((4j+1)r−1)=ν2(4j)+ν2(r)≥k.\nu_2\left((4j+1)^r-1\right)=\nu_2(4j)+\nu_2(r)\geq k.

References

  1. [1]N. Beneš, L. Brim, J. Kadlečaj, S. Pastva, and D. Šafránek. Exploring attractor bifurcations in boolean networks. BMC Bioinformatics, 23:173, 2022.
  2. [2]A. Bors, D. Panario, and Q. Wang. Functional graphs of generalized cyclotomic mappings of finite fields. Memoirs of the European Mathematical Society, 23:1–270, 2025.arxiv.org/abs/2304.00181
  3. [3]C. Bouvier, A. Canteaut, and L. Perrin. On the algebraic degree of iterated power functions. Designs, Codes and Cryptography, 91:997–1033, 2023.DOI
  4. [4]G. Deng. Isomorphic digraphs from affine maps of finite cyclic groups. International Scholarly Research Notices, 2013:398641, 2013.DOI
  5. [5]J. Eichenauer-Herrmann, E. Herrmann, and S. Wegenkittl. A survey of quadratic and inversive congruential pseudorandom numbers. In Monte Carlo and Quasi- Monte Carlo Methods, volume 127 of Lecture Notes in Statistics, pages 66–97. Springer, 1998.
  6. [6]P. Flajolet and A. M. Odlyzko. Random mapping statistics. In Advances in Cryptology — EUROCRYPT ’89, volume 434, pages 329–354, Berlin, Heidelberg, 1990. Springer Berlin Heidelberg.
  7. [7]C. Kadelka, M. Wheeler, A. Veliz-Cuba, D. Murrugarra, and R. Laubenbacher. Modularity of biological systems: a link between structure and function. Journal of the Royal Society Interface, 20:20230505, 2023.
  8. [8]N. Koblitz. p-adic Numbers, p-adic Analysis, and Zeta-Functions, volume 58 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2 edition, 1984.
  9. [9]M. Manea. Some aⁿ ±bⁿ problems in number theory. Mathematics Magazine, 79:140–145, 2006.
  10. [10]M. Martelli. Introduction to Discrete Dynamical Systems and Chaos. John Wiley & Sons, New York, 1999.DOI
  11. [11]R. Martins, D. Panario, and C. Qureshi. 8. A survey on iterations of mappings over finite fields, pages 135–172. De Gruyter, Berlin, Boston, 2019.
  12. [12]H. Niederreiter and A. Winterhof. Cyclotomic ℛ-orthomorphisms of finite fields. Discrete Mathematics, 295:161–171, 2005.DOI
  13. [13]H. Niederreiter and A. Winterhof. Applied Number Theory. Springer, Cham, 2015.DOI
  14. [14]D. H. Nyang and J. S. Song. Fast digital signature scheme based on the quadratic residue problem. Electronics Letters, 33:205–206, 1997.DOI
  15. [15]D. Panario and L. Reis. The functional graph of linear maps over finite fields and applications. Designs, Codes and Cryptography, 87:437–453, 2019.DOI
  16. [16]C. Qureshi and D. Panario. Rédei actions on finite fields and multiplication map in cyclic groups. SIAM Journal on Discrete Mathematics, 29:1486–1503, 2015.DOI
  17. [17]C. Qureshi and D. Panario. The graph structure of the chebyshev polynomial over finite fields and applications. Designs, Codes and Cryptography, 87:393–416, 2019.
  18. [18]M. Sha. Digraphs from endomorphisms of finite cyclic groups. The Journal of Combinatorial Mathematics and Combinatorics, 83:105–120, 2012.
  19. [19]R. P. Stanley. Enumerative Combinatorics, volume 1 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2nd edition, 2011.
  20. [20]A. Topuzoğlu and A. Winterhof. Pseudorandom sequences. In Topics in geometry, coding theory and cryptography, volume 6 of Algebra. Appl., pages 135–166. Springer, Dordrecht, 2007.
  21. [21]Q. Wang. Cyclotomic mapping permutation polynomials over finite fields. In Sequences, Subsequences, and Consequences, pages 119–128, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.DOI
  22. [22]A. Winterhof. Recent results on recursive nonlinear pseudorandom number generators (invited paper). In Sequences and their applications—SETA 2010, volume 6338 of Lecture Notes in Comput. Sci., pages 113–124. Springer, Berlin, 2010.DOI

Paper details

vlnc:W_8edtwben
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents