American Institute of Mathematical Sciences

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

Cycle structure of iterating Redei functions

Claudio Qureshi 1, , Daniel Panario 2, and  Rodrigo Martins 3,

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.

Keywords: Cycle structure, Redei functions, one-dimensional dynamics.
Mathematics Subject Classification: Primary: 11T71; Secondary: 94A62.
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.

[2]

R. Brent and J. Pollard, Factorization of the eighth Fermat number, Math. Comput., 36 (1981), 627-630.  doi: 10.2307/2007666.

[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.

[4]

D. A. Cox, Primes of the Form $x^2+ny^2$: Fermat, Class Field Theory and Complex Multiplication, Wiley-Interscience, 1989.

[5]

FIPS PUB 186-4, Digital Signature Standard (DSS), Federal Information Processing Standards Publication, NIST, 2013.

[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.

[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.

[8]

NIST Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, NIST, 2007.

[9]

R. Nobauer, Cryptoanalysis of the Rédei scheme, Contrib. General Algebra, 3 (1984), 255-264. 

[10]

R. Nobauer, Key distribution systems based on polynomial functions and Rédei functions, Probl. Contr. Inf. Theory, 15 (1986), 91-100. 

[11]

R. Pieper, Cryptanalysis of Rédei-and Dickson permutations on arbitrary finite rings, AAECC, 4 (1993), 59-76.  doi: 10.1007/BF01270400.

[12]

J. M. Pollard, A monte carlo method for factorization, BIT, 15 (1975), 331-334. 

[13]

J. M. Pollard, Monte carlo methods for index computation (mod $p$), Math. Comp., 32 (1978), 918-924.  doi: 10.2307/2006496.

[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.

[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.

[16]

M. Sha, Digraphs from endomorphisms of finite cyclic groups, J. Combin. Math. Combin. Comp., 83 (2012), 105-120. 

[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.

[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.

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.

[2]

R. Brent and J. Pollard, Factorization of the eighth Fermat number, Math. Comput., 36 (1981), 627-630.  doi: 10.2307/2007666.

[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.

[4]

D. A. Cox, Primes of the Form $x^2+ny^2$: Fermat, Class Field Theory and Complex Multiplication, Wiley-Interscience, 1989.

[5]

FIPS PUB 186-4, Digital Signature Standard (DSS), Federal Information Processing Standards Publication, NIST, 2013.

[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.

[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.

[8]

NIST Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, NIST, 2007.

[9]

R. Nobauer, Cryptoanalysis of the Rédei scheme, Contrib. General Algebra, 3 (1984), 255-264. 

[10]

R. Nobauer, Key distribution systems based on polynomial functions and Rédei functions, Probl. Contr. Inf. Theory, 15 (1986), 91-100. 

[11]

R. Pieper, Cryptanalysis of Rédei-and Dickson permutations on arbitrary finite rings, AAECC, 4 (1993), 59-76.  doi: 10.1007/BF01270400.

[12]

J. M. Pollard, A monte carlo method for factorization, BIT, 15 (1975), 331-334. 

[13]

J. M. Pollard, Monte carlo methods for index computation (mod $p$), Math. Comp., 32 (1978), 918-924.  doi: 10.2307/2006496.

[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.

[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.

[16]

M. Sha, Digraphs from endomorphisms of finite cyclic groups, J. Combin. Math. Combin. Comp., 83 (2012), 105-120. 

[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.

[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.

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$
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Sebastian van Strien. One-dimensional dynamics in the new millennium. Discrete and Continuous Dynamical Systems, 2010, 27 (2) : 557-588. doi: 10.3934/dcds.2010.27.557
[2]

Francisco J. López-Hernández. Dynamics of induced homeomorphisms of one-dimensional solenoids. Discrete and Continuous Dynamical Systems, 2018, 38 (9) : 4243-4257. doi: 10.3934/dcds.2018185
[3]

Zhi-An Wang, Kun Zhao. Global dynamics and diffusion limit of a one-dimensional repulsive chemotaxis model. Communications on Pure and Applied Analysis, 2013, 12 (6) : 3027-3046. doi: 10.3934/cpaa.2013.12.3027
[4]

Charles Nguyen, Stephen Pankavich. A one-dimensional kinetic model of plasma dynamics with a transport field. Evolution Equations and Control Theory, 2014, 3 (4) : 681-698. doi: 10.3934/eect.2014.3.681
[5]

Dominik Hafemeyer, Florian Mannel, Ira Neitzel, Boris Vexler. Finite element error estimates for one-dimensional elliptic optimal control by BV-functions. Mathematical Control and Related Fields, 2020, 10 (2) : 333-363. doi: 10.3934/mcrf.2019041
[6]

Evelyn Herberg, Michael Hinze. Variational discretization of one-dimensional elliptic optimal control problems with BV functions based on the mixed formulation. Mathematical Control and Related Fields, 2022  doi: 10.3934/mcrf.2022013
[7]

Xin Liu, Yongjin Lu, Xin-Guang Yang. Stability and dynamics for a nonlinear one-dimensional full compressible non-Newtonian fluids. Evolution Equations and Control Theory, 2021, 10 (2) : 365-384. doi: 10.3934/eect.2020071
[8]

Julián López-Gómez, Marcela Molina-Meyer, Andrea Tellini. Intricate bifurcation diagrams for a class of one-dimensional superlinear indefinite problems of interest in population dynamics. Conference Publications, 2013, 2013 (special) : 515-524. doi: 10.3934/proc.2013.2013.515
[9]

Ben Duan, Zhen Luo. Dynamics of vacuum states for one-dimensional full compressible Navier-Stokes equations. Communications on Pure and Applied Analysis, 2013, 12 (6) : 2543-2564. doi: 10.3934/cpaa.2013.12.2543
[10]

Maria do Carmo Pacheco de Toledo, Sergio Muniz Oliva. A discretization scheme for an one-dimensional reaction-diffusion equation with delay and its dynamics. Discrete and Continuous Dynamical Systems, 2009, 23 (3) : 1041-1060. doi: 10.3934/dcds.2009.23.1041
[11]

Takeshi Fukao, Shuji Yoshikawa, Saori Wada. Structure-preserving finite difference schemes for the Cahn-Hilliard equation with dynamic boundary conditions in the one-dimensional case. Communications on Pure and Applied Analysis, 2017, 16 (5) : 1915-1938. doi: 10.3934/cpaa.2017093
[12]

Amin Sakzad, Mohammad-Reza Sadeghi, Daniel Panario. Cycle structure of permutation functions over finite fields and their applications. Advances in Mathematics of Communications, 2012, 6 (3) : 347-361. doi: 10.3934/amc.2012.6.347
[13]

Maria João Costa. Chaotic behaviour of one-dimensional horseshoes. Discrete and Continuous Dynamical Systems, 2003, 9 (3) : 505-548. doi: 10.3934/dcds.2003.9.505
[14]

Yunping Jiang. On a question of Katok in one-dimensional case. Discrete and Continuous Dynamical Systems, 2009, 24 (4) : 1209-1213. doi: 10.3934/dcds.2009.24.1209
[15]

Nguyen Dinh Cong, Roberta Fabbri. On the spectrum of the one-dimensional Schrödinger operator. Discrete and Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 541-554. doi: 10.3934/dcdsb.2008.9.541
[16]

James Nolen, Jack Xin. KPP fronts in a one-dimensional random drift. Discrete and Continuous Dynamical Systems - B, 2009, 11 (2) : 421-442. doi: 10.3934/dcdsb.2009.11.421
[17]

Nicolai T. A. Haydn. Phase transitions in one-dimensional subshifts. Discrete and Continuous Dynamical Systems, 2013, 33 (5) : 1965-1973. doi: 10.3934/dcds.2013.33.1965
[18]

Rogério Martins. One-dimensional attractor for a dissipative system with a cylindrical phase space. Discrete and Continuous Dynamical Systems, 2006, 14 (3) : 533-547. doi: 10.3934/dcds.2006.14.533
[19]

Gabriele Bonanno, Giuseppina D'Aguì, Angela Sciammetta. One-dimensional nonlinear boundary value problems with variable exponent. Discrete and Continuous Dynamical Systems - S, 2018, 11 (2) : 179-191. doi: 10.3934/dcdss.2018011
[20]

Anton A. Kutsenko. Isomorphism between one-dimensional and multidimensional finite difference operators. Communications on Pure and Applied Analysis, 2021, 20 (1) : 359-368. doi: 10.3934/cpaa.2020270

2021 Impact Factor: 1.015

Tools

Metrics

  • PDF downloads (133)
  • HTML views (61)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy