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

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 & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 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 & 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 & 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 & Related Fields, 2020, 10 (2) : 333-363. doi: 10.3934/mcrf.2019041
[6]

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

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

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 & Continuous Dynamical Systems - A, 2009, 23 (3) : 1041-1060. doi: 10.3934/dcds.2009.23.1041
[9]

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
[10]

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 & Applied Analysis, 2017, 16 (5) : 1915-1938. doi: 10.3934/cpaa.2017093
[11]

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

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

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

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

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

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

Dirk Blömker, Bernhard Gawron, Thomas Wanner. Nucleation in the one-dimensional stochastic Cahn-Hilliard model. Discrete & Continuous Dynamical Systems - A, 2010, 27 (1) : 25-52. doi: 10.3934/dcds.2010.27.25
[18]

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

Antoine Mellet, Jean-Michel Roquejoffre, Yannick Sire. Generalized fronts for one-dimensional reaction-diffusion equations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 303-312. doi: 10.3934/dcds.2010.26.303
[20]

Blanca Ayuso, José A. Carrillo, Chi-Wang Shu. Discontinuous Galerkin methods for the one-dimensional Vlasov-Poisson system. Kinetic & Related Models, 2011, 4 (4) : 955-989. doi: 10.3934/krm.2011.4.955

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (44)
  • HTML views (55)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences