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

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

Metrics

  • PDF downloads (72)
  • HTML views (58)
  • Cited by (3)

[Back to Top]