# American Institute of Mathematical Sciences

May  2017, 11(2): 397-407. doi: 10.3934/amc.2017034

## Cycle structure of iterating Redei functions

 1 Institute of Mathematics, State University of Campinas, Brazil 2 School of Mathematics and Statistics, Carleton University, Canada 3 Academic Department of Mathematics, UTFPR, Brazil

Received  February 2016 Revised  March 2016 Published  May 2017

Fund Project: C. Qureshi is supported by FAPESP 2012/10600-2 and CNPq 158670/2015-9; D. Panario is supported by NSERC.

Vasiga and Shallit [17] study tails and cycles in orbits of iterations of quadratic polynomials over prime fields. These results were extended to repeated exponentiation by Chou and Shparlinski [3]. We show, using the quadratic reciprocity law, that it is possible to extend these results to Rédei functions over prime fields.

Citation: Claudio Qureshi, Daniel Panario, Rodrigo Martins. Cycle structure of iterating Redei functions. Advances in Mathematics of Communications, 2017, 11 (2) : 397-407. doi: 10.3934/amc.2017034
##### References:
 [1] L. Blum, M. Blum and M. Shub, A simple unpredictable pseudo-random number generator, SIAM J. Comput., 15 (1986), 364-383.  doi: 10.1137/0215025.  Google Scholar [2] R. Brent and J. Pollard, Factorization of the eighth Fermat number, Math. Comput., 36 (1981), 627-630.  doi: 10.2307/2007666.  Google Scholar [3] W. Chou and I. E. Shparlinski, On the cycle structure of repeated exponentiation modulo a prime, J. Number Theory, 107 (2004), 345-356.  doi: 10.1016/j.jnt.2004.04.005.  Google Scholar [4] D. A. Cox, Primes of the Form $x^2+ny^2$: Fermat, Class Field Theory and Complex Multiplication, Wiley-Interscience, 1989.  Google Scholar [5] FIPS PUB 186-4, Digital Signature Standard (DSS), Federal Information Processing Standards Publication, NIST, 2013. Google Scholar [6] R. Lidl and W. B. Müller, Generalization of the Fibonacci pseudoprime test, Discrete Math., 92 (1991), 211-220.  doi: 10.1016/0012-365X(91)90282-7.  Google Scholar [7] W. Meidl and A. Winterhof, On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions, Finite Fields Appl., 13 (2007), 628-634.  doi: 10.1016/j.ffa.2005.10.001.  Google Scholar [8] NIST Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, NIST, 2007. Google Scholar [9] R. Nobauer, Cryptoanalysis of the Rédei scheme, Contrib. General Algebra, 3 (1984), 255-264.   Google Scholar [10] R. Nobauer, Key distribution systems based on polynomial functions and Rédei functions, Probl. Contr. Inf. Theory, 15 (1986), 91-100.   Google Scholar [11] R. Pieper, Cryptanalysis of Rédei-and Dickson permutations on arbitrary finite rings, AAECC, 4 (1993), 59-76.  doi: 10.1007/BF01270400.  Google Scholar [12] J. M. Pollard, A monte carlo method for factorization, BIT, 15 (1975), 331-334.   Google Scholar [13] J. M. Pollard, Monte carlo methods for index computation (mod $p$), Math. Comp., 32 (1978), 918-924.  doi: 10.2307/2006496.  Google Scholar [14] C. Qureshi and D. Panario, Rédei actions on finite fields and multiplication map in cyclic groups, SIAM J. Discrete Math., 29 (2015), 1486-1503.  doi: 10.1137/140993338.  Google Scholar [15] A. Sakzad, M. Sadeghi and D. Panario, Cycle structure of permutation functions over finite fields and their applications, Adv. Math. Commun., 6 (2012), 347-361.  doi: 10.3934/amc.2012.6.347.  Google Scholar [16] M. Sha, Digraphs from endomorphisms of finite cyclic groups, J. Combin. Math. Combin. Comp., 83 (2012), 105-120.   Google Scholar [17] T. Vasiga and J. Shallit, On the iteration of certain quadratic maps over $GF(p)$, Discrete Math., 277 (2004), 219-240.  doi: 10.1016/S0012-365X(03)00158-4.  Google Scholar [18] M. Wiener and R. Zuccherato, Faster attacks on elliptic curve cryptosystems, in Selected Areas in Cryptography, 1998,190-200. doi: 10.1007/3-540-48892-8_15.  Google Scholar

show all references

##### References:
 [1] L. Blum, M. Blum and M. Shub, A simple unpredictable pseudo-random number generator, SIAM J. Comput., 15 (1986), 364-383.  doi: 10.1137/0215025.  Google Scholar [2] R. Brent and J. Pollard, Factorization of the eighth Fermat number, Math. Comput., 36 (1981), 627-630.  doi: 10.2307/2007666.  Google Scholar [3] W. Chou and I. E. Shparlinski, On the cycle structure of repeated exponentiation modulo a prime, J. Number Theory, 107 (2004), 345-356.  doi: 10.1016/j.jnt.2004.04.005.  Google Scholar [4] D. A. Cox, Primes of the Form $x^2+ny^2$: Fermat, Class Field Theory and Complex Multiplication, Wiley-Interscience, 1989.  Google Scholar [5] FIPS PUB 186-4, Digital Signature Standard (DSS), Federal Information Processing Standards Publication, NIST, 2013. Google Scholar [6] R. Lidl and W. B. Müller, Generalization of the Fibonacci pseudoprime test, Discrete Math., 92 (1991), 211-220.  doi: 10.1016/0012-365X(91)90282-7.  Google Scholar [7] W. Meidl and A. Winterhof, On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions, Finite Fields Appl., 13 (2007), 628-634.  doi: 10.1016/j.ffa.2005.10.001.  Google Scholar [8] NIST Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, NIST, 2007. Google Scholar [9] R. Nobauer, Cryptoanalysis of the Rédei scheme, Contrib. General Algebra, 3 (1984), 255-264.   Google Scholar [10] R. Nobauer, Key distribution systems based on polynomial functions and Rédei functions, Probl. Contr. Inf. Theory, 15 (1986), 91-100.   Google Scholar [11] R. Pieper, Cryptanalysis of Rédei-and Dickson permutations on arbitrary finite rings, AAECC, 4 (1993), 59-76.  doi: 10.1007/BF01270400.  Google Scholar [12] J. M. Pollard, A monte carlo method for factorization, BIT, 15 (1975), 331-334.   Google Scholar [13] J. M. Pollard, Monte carlo methods for index computation (mod $p$), Math. Comp., 32 (1978), 918-924.  doi: 10.2307/2006496.  Google Scholar [14] C. Qureshi and D. Panario, Rédei actions on finite fields and multiplication map in cyclic groups, SIAM J. Discrete Math., 29 (2015), 1486-1503.  doi: 10.1137/140993338.  Google Scholar [15] A. Sakzad, M. Sadeghi and D. Panario, Cycle structure of permutation functions over finite fields and their applications, Adv. Math. Commun., 6 (2012), 347-361.  doi: 10.3934/amc.2012.6.347.  Google Scholar [16] M. Sha, Digraphs from endomorphisms of finite cyclic groups, J. Combin. Math. Combin. Comp., 83 (2012), 105-120.   Google Scholar [17] T. Vasiga and J. Shallit, On the iteration of certain quadratic maps over $GF(p)$, Discrete Math., 277 (2004), 219-240.  doi: 10.1016/S0012-365X(03)00158-4.  Google Scholar [18] M. Wiener and R. Zuccherato, Faster attacks on elliptic curve cryptosystems, in Selected Areas in Cryptography, 1998,190-200. doi: 10.1007/3-540-48892-8_15.  Google Scholar
]) illustrates the inductive definition of $T_V$ when $V$ is a $\nu$-series with four components $V=(\nu_1,\nu_2,\nu_3,\nu_4)$. A node $v$ labelled by a rooted tree $T$ indicates that $v$ is the root of a tree isomorphic to $T$">Figure 1.  This figure (taken from [14]) illustrates the inductive definition of $T_V$ when $V$ is a $\nu$-series with four components $V=(\nu_1,\nu_2,\nu_3,\nu_4)$. A node $v$ labelled by a rooted tree $T$ indicates that $v$ is the root of a tree isomorphic to $T$
 [1] Akane Kawaharada. Singular function emerging from one-dimensional elementary cellular automaton Rule 150. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021125 [2] Madalina Petcu, Roger Temam. The one dimensional shallow water equations with Dirichlet boundary conditions on the velocity. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 209-222. doi: 10.3934/dcdss.2011.4.209 [3] Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021070 [4] Anastasiia Panchuk, Frank Westerhoff. Speculative behavior and chaotic asset price dynamics: On the emergence of a bandcount accretion bifurcation structure. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021117 [5] Prabir Panja, Soovoojeet Jana, Shyamal kumar Mondal. Dynamics of a stage structure prey-predator model with ratio-dependent functional response and anti-predator behavior of adult prey. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 391-405. doi: 10.3934/naco.2020033 [6] Mia Jukić, Hermen Jan Hupkes. Dynamics of curved travelling fronts for the discrete Allen-Cahn equation on a two-dimensional lattice. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3163-3209. doi: 10.3934/dcds.2020402 [7] Yusi Fan, Chenrui Yao, Liangyun Chen. Structure of sympathetic Lie superalgebras. Electronic Research Archive, , () : -. doi: 10.3934/era.2021020 [8] Muhammad Aslam Noor, Khalida Inayat Noor. Properties of higher order preinvex functions. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 431-441. doi: 10.3934/naco.2020035 [9] Rafael G. L. D'Oliveira, Marcelo Firer. Minimum dimensional Hamming embeddings. Advances in Mathematics of Communications, 2017, 11 (2) : 359-366. doi: 10.3934/amc.2017029 [10] Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409 [11] Wei Liu, Pavel Krejčí, Guoju Ye. Continuity properties of Prandtl-Ishlinskii operators in the space of regulated functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3783-3795. doi: 10.3934/dcdsb.2017190 [12] Daoyuan Fang, Ting Zhang. Compressible Navier-Stokes equations with vacuum state in one dimension. Communications on Pure & Applied Analysis, 2004, 3 (4) : 675-694. doi: 10.3934/cpaa.2004.3.675 [13] Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2891-2905. doi: 10.3934/dcds.2020390 [14] Youjun Deng, Hongyu Liu, Xianchao Wang, Dong Wei, Liyan Zhu. Simultaneous recovery of surface heat flux and thickness of a solid structure by ultrasonic measurements. Electronic Research Archive, , () : -. doi: 10.3934/era.2021027 [15] Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136 [16] Wided Kechiche. Global attractor for a nonlinear Schrödinger equation with a nonlinearity concentrated in one point. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021031 [17] Jianfeng Lv, Yan Gao, Na Zhao. The viability of switched nonlinear systems with piecewise smooth Lyapunov functions. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1825-1843. doi: 10.3934/jimo.2020048 [18] Christoforidou Amalia, Christian-Oliver Ewald. A lattice method for option evaluation with regime-switching asset correlation structure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1729-1752. doi: 10.3934/jimo.2020042 [19] Lei Lei, Wenli Ren, Cuiling Fan. The differential spectrum of a class of power functions over finite fields. Advances in Mathematics of Communications, 2021, 15 (3) : 525-537. doi: 10.3934/amc.2020080 [20] Adrian Viorel, Cristian D. Alecsa, Titus O. Pinţa. Asymptotic analysis of a structure-preserving integrator for damped Hamiltonian systems. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3319-3341. doi: 10.3934/dcds.2020407

2019 Impact Factor: 0.734