Advanced Search
Article Contents
Article Contents

Cycle structure of iterating Redei functions

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

Abstract Full Text(HTML) Figure(1) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 11T71; Secondary: 94A62.


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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$

  •   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.
      R. Brent  and  J. Pollard , Factorization of the eighth Fermat number, Math. Comput., 36 (1981) , 627-630.  doi: 10.2307/2007666.
      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.
      D. A. Cox, Primes of the Form $x^2+ny^2$: Fermat, Class Field Theory and Complex Multiplication, Wiley-Interscience, 1989.
      FIPS PUB 186-4, Digital Signature Standard (DSS), Federal Information Processing Standards Publication, NIST, 2013.
      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.
      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.
      NIST Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, NIST, 2007.
      R. Nobauer , Cryptoanalysis of the Rédei scheme, Contrib. General Algebra, 3 (1984) , 255-264. 
      R. Nobauer , Key distribution systems based on polynomial functions and Rédei functions, Probl. Contr. Inf. Theory, 15 (1986) , 91-100. 
      R. Pieper , Cryptanalysis of Rédei-and Dickson permutations on arbitrary finite rings, AAECC, 4 (1993) , 59-76.  doi: 10.1007/BF01270400.
      J. M. Pollard , A monte carlo method for factorization, BIT, 15 (1975) , 331-334. 
      J. M. Pollard , Monte carlo methods for index computation (mod $p$), Math. Comp., 32 (1978) , 918-924.  doi: 10.2307/2006496.
      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.
      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.
      M. Sha , Digraphs from endomorphisms of finite cyclic groups, J. Combin. Math. Combin. Comp., 83 (2012) , 105-120. 
      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.
      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.
  • 加载中



Article Metrics

HTML views(331) PDF downloads(162) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint