On the degree growth in some polynomial dynamical systems and nonlinear pseudorandom number generators
HTML articles powered by AMS MathViewer
- by Alina Ostafe and Igor E. Shparlinski PDF
- Math. Comp. 79 (2010), 501-511 Request permission
Abstract:
In this paper we study a class of dynamical systems generated by iterations of multivariate polynomials and estimate the degree growth of these iterations. We use these estimates to bound exponential sums along the orbits of these dynamical systems and show that they admit much stronger estimates than in the general case and thus can be of use for pseudorandom number generation.References
- V. I. Arnol′d, The Fermat-Euler dynamical system and the statistics of the arithmetic of geometric progressions, Funktsional. Anal. i Prilozhen. 37 (2003), no. 1, 1–18, 95 (Russian, with Russian summary); English transl., Funct. Anal. Appl. 37 (2003), no. 1, 1–15. MR 1988005, DOI 10.1023/A:1022915825459
- V. Arnold, Number-theoretical turbulence in Fermat-Euler arithmetics and large Young diagrams geometry statistics, J. Math. Fluid Mech. 7 (2005), no. suppl. 1, S4–S50. MR 2126128, DOI 10.1007/s00021-004-0130-x
- V. Arnold, Ergodic and arithmetical properties of geometrical progression’s dynamics and of its orbits, Mosc. Math. J. 5 (2005), no. 1, 5–22 (English, with English and Russian summaries). MR 2153464, DOI 10.17323/1609-4514-2005-5-1-5-22
- Simon R. Blackburn, Domingo Gomez-Perez, Jaime Gutierrez, and Igor E. Shparlinski, Predicting the inversive generator, Cryptography and coding, Lecture Notes in Comput. Sci., vol. 2898, Springer, Berlin, 2003, pp. 264–275. MR 2090938, DOI 10.1007/978-3-540-40974-8_{2}1
- Simon R. Blackburn, Domingo Gomez-Perez, Jaime Gutierrez, and Igor E. Shparlinski, Predicting nonlinear pseudorandom number generators, Math. Comp. 74 (2005), no. 251, 1471–1494. MR 2137013, DOI 10.1090/S0025-5718-04-01698-9
- J. Bourgain, Mordell’s exponential sum estimate revisited, J. Amer. Math. Soc. 18 (2005), no. 2, 477–499. MR 2137982, DOI 10.1090/S0894-0347-05-00476-5
- Mei-Chu Chang, On a problem of Arnold on uniform distribution, J. Funct. Anal. 242 (2007), no. 1, 272–280. MR 2274023, DOI 10.1016/j.jfa.2006.06.009
- Wun-Seng Chou and Igor E. Shparlinski, On the cycle structure of repeated exponentiation modulo a prime, J. Number Theory 107 (2004), no. 2, 345–356. MR 2072394, DOI 10.1016/j.jnt.2004.04.005
- Stephen D. Cohen and Dirk Hachenberger, The dynamics of linearized polynomials, Proc. Edinburgh Math. Soc. (2) 43 (2000), no. 1, 113–128. MR 1744703, DOI 10.1017/S0013091500020733
- Omar Colón-Reyes, Abdul Salam Jarrah, Reinhard Laubenbacher, and Bernd Sturmfels, Monomial dynamical systems over finite fields, Complex Systems 16 (2006), no. 4, 333–342. MR 2293353
- S. Contini and I. E. Shparlinski, ‘On Stern’s attack against secret truncated linear congruential generators’, Lect. Notes in Comput. Sci., Springer-Verlag, Berlin, 3574 (2005), 52–60.
- P. Deligne, ‘Applications de la formule des traces aux sommes trigonométriques’, Lect. Notes in Mathematics, Springer-Verlag, Berlin, 569 (1977), 168–232.
- Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456, DOI 10.1007/BFb0093404
- Graham Everest and Thomas Ward, Heights of polynomials and entropy in algebraic dynamics, Universitext, Springer-Verlag London, Ltd., London, 1999. MR 1700272, DOI 10.1007/978-1-4471-3898-3
- Sergey Fomin and Andrei Zelevinsky, The Laurent phenomenon, Adv. in Appl. Math. 28 (2002), no. 2, 119–144. MR 1888840, DOI 10.1006/aama.2001.0770
- John B. Friedlander, Jan Hansen, and Igor E. Shparlinski, Character sums with exponential functions, Mathematika 47 (2000), no. 1-2, 75–85 (2002). MR 1924489, DOI 10.1112/S0025579300015734
- John B. Friedlander, Carl Pomerance, and Igor E. Shparlinski, Period of the power generator and small values of Carmichael’s function, Math. Comp. 70 (2001), no. 236, 1591–1605. MR 1836921, DOI 10.1090/S0025-5718-00-01282-5
- John B. Friedlander and Igor E. Shparlinski, On the distribution of the power generator, Math. Comp. 70 (2001), no. 236, 1575–1589. MR 1836920, DOI 10.1090/S0025-5718-00-01283-7
- Alan M. Frieze, Johan Håstad, Ravi Kannan, Jeffrey C. Lagarias, and Adi Shamir, Reconstructing truncated integer variables satisfying linear congruences, SIAM J. Comput. 17 (1988), no. 2, 262–280. Special issue on cryptography. MR 935340, DOI 10.1137/0217016
- Frances Griffin, Harald Niederreiter, and Igor E. Shparlinski, On the distribution of nonlinear recursive congruential pseudorandom numbers of higher orders, Applied algebra, algebraic algorithms and error-correcting codes (Honolulu, HI, 1999) Lecture Notes in Comput. Sci., vol. 1719, Springer, Berlin, 1999, pp. 87–93. MR 1846485, DOI 10.1007/3-540-46796-3_{9}
- Domingo Gómez, Jaime Gutierrez, and Álvar Ibeas, Attacking the Pollard generator, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5518–5523. MR 2300710, DOI 10.1109/TIT.2006.885451
- Jaime Gutierrez and Domingo Gomez-Perez, Iterations of multivariate polynomials and discrepancy of pseudorandom numbers, Applied algebra, algebraic algorithms and error-correcting codes (Melbourne, 2001) Lecture Notes in Comput. Sci., vol. 2227, Springer, Berlin, 2001, pp. 192–199. MR 1913465, DOI 10.1007/3-540-45624-4_{2}0
- Domingo Gomez-Perez, Jaime Gutierrez, and Igor E. Shparlinski, Exponential sums with Dickson polynomials, Finite Fields Appl. 12 (2006), no. 1, 16–25. MR 2190184, DOI 10.1016/j.ffa.2004.08.001
- Jaime Gutierrez and Álvar Ibeas, Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits, Des. Codes Cryptogr. 45 (2007), no. 2, 199–212. MR 2341883, DOI 10.1007/s10623-007-9112-3
- Jaime Gutierrez and Arne Winterhof, Exponential sums of nonlinear congruential pseudorandom number generators with Rédei functions, Finite Fields Appl. 14 (2008), no. 2, 410–416. MR 2401984, DOI 10.1016/j.ffa.2007.03.004
- Rafe Jones, The density of prime divisors in the arithmetic dynamics of quadratic polynomials, J. Lond. Math. Soc. (2) 78 (2008), no. 2, 523–544. MR 2439638, DOI 10.1112/jlms/jdn034
- Antoine Joux and Jacques Stern, Lattice reduction: a toolbox for the cryptanalyst, J. Cryptology 11 (1998), no. 3, 161–185. MR 1633944, DOI 10.1007/s001459900042
- Nicholas M. Katz, Estimates for “singular” exponential sums, Internat. Math. Res. Notices 16 (1999), 875–899. MR 1715519, DOI 10.1155/S1073792899000458
- Hugo Krawczyk, How to predict congruential generators, J. Algorithms 13 (1992), no. 4, 527–545. MR 1187200, DOI 10.1016/0196-6774(92)90054-G
- L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0419394
- J. C. Lagarias, Pseudorandom number generators in cryptography and number theory, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 115–143. MR 1095554, DOI 10.1090/psapm/042/1095554
- Rudolf Lidl and Harald Niederreiter, Finite fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M. Cohn. MR 1429394
- Sandra Marcello, Sur la dynamique arithmétique des automorphismes de l’espace affine, Bull. Soc. Math. France 131 (2003), no. 2, 229–257 (French, with English and French summaries). MR 1988948, DOI 10.24033/bsmf.2441
- Greg Martin and Carl Pomerance, The iterated Carmichael $\lambda$-function and the number of cycles of the power generator, Acta Arith. 118 (2005), no. 4, 305–335. MR 2165548, DOI 10.4064/aa118-4-1
- Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447, DOI 10.1090/S0002-9904-1978-14532-7
- Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
- Harald Niederreiter and Igor E. Shparlinski, On the distribution and lattice structure of nonlinear congruential pseudorandom numbers, Finite Fields Appl. 5 (1999), no. 3, 246–253. MR 1702905, DOI 10.1006/ffta.1999.0257
- Harald Niederreiter and Igor E. Shparlinski, On the distribution of inversive congruential pseudorandom numbers in parts of the period, Math. Comp. 70 (2001), no. 236, 1569–1574. MR 1836919, DOI 10.1090/S0025-5718-00-01273-4
- Harald Niederreiter and Igor E. Shparlinski, On the average distribution of inversive pseudorandom numbers, Finite Fields Appl. 8 (2002), no. 4, 491–503. MR 1933620
- Harald Niederreiter and Igor E. Shparlinski, Dynamical systems generated by rational functions, Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 2003) Lecture Notes in Comput. Sci., vol. 2643, Springer, Berlin, 2003, pp. 6–17. MR 2042407, DOI 10.1007/3-540-44828-4_{2}
- Harald Niederreiter and Arne Winterhof, Exponential sums for nonlinear recurring sequences, Finite Fields Appl. 14 (2008), no. 1, 59–64. MR 2381476, DOI 10.1016/j.ffa.2006.09.010
- Igor E. Shparlinski, On some dynamical systems in finite fields and residue rings, Discrete Contin. Dyn. Syst. 17 (2007), no. 4, 901–917. MR 2276481, DOI 10.3934/dcds.2007.17.901
- Joseph H. Silverman, The arithmetic of dynamical systems, Graduate Texts in Mathematics, vol. 241, Springer, New York, 2007. MR 2316407, DOI 10.1007/978-0-387-69904-2
- Joseph H. Silverman, Variation of periods modulo $p$ in arithmetic dynamics, New York J. Math. 14 (2008), 601–616. MR 2448661
- Alev Topuzoğlu and Arne Winterhof, Pseudorandom sequences, Topics in geometry, coding theory and cryptography, Algebr. Appl., vol. 6, Springer, Dordrecht, 2007, pp. 135–166. MR 2278037, DOI 10.1007/1-4020-5334-4_{4}
- Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over $\textrm {GF}(p)$, Discrete Math. 277 (2004), no. 1-3, 219–240. MR 2033734, DOI 10.1016/S0012-365X(03)00158-4
Additional Information
- Alina Ostafe
- Affiliation: Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190 CH-8057, Zürich, Switzerland
- MR Author ID: 884181
- Email: alina.ostafe@math.uzh.ch
- Igor E. Shparlinski
- Affiliation: Department of Computing, Macquarie University, NSW 2109, Australia
- MR Author ID: 192194
- Email: igor@ics.mq.edu.au
- Received by editor(s): February 23, 2009
- Received by editor(s) in revised form: March 9, 2009
- Published electronically: July 7, 2009
- © Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 79 (2010), 501-511
- MSC (2000): Primary 11K45, 11T23, 37A45, 37F10
- DOI: https://doi.org/10.1090/S0025-5718-09-02271-6
- MathSciNet review: 2552237