On the degree growth in some polynomial dynamical systems and nonlinear pseudorandom number generators
Authors:
Alina Ostafe and Igor E. Shparlinski
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
Published electronically:
July 7, 2009
MathSciNet review:
2552237
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
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.
- 1. 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, https://doi.org/10.1023/A:1022915825459
- 2. 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, https://doi.org/10.1007/s00021-004-0130-x
- 3. 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, https://doi.org/10.17323/1609-4514-2005-5-1-5-22
- 4. 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, https://doi.org/10.1007/978-3-540-40974-8_21
- 5. 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, https://doi.org/10.1090/S0025-5718-04-01698-9
- 6. J. Bourgain, Mordell’s exponential sum estimate revisited, J. Amer. Math. Soc. 18 (2005), no. 2, 477–499. MR 2137982, https://doi.org/10.1090/S0894-0347-05-00476-5
- 7. Mei-Chu Chang, On a problem of Arnold on uniform distribution, J. Funct. Anal. 242 (2007), no. 1, 272–280. MR 2274023, https://doi.org/10.1016/j.jfa.2006.06.009
- 8. 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, https://doi.org/10.1016/j.jnt.2004.04.005
- 9. Stephen D. Cohen and Dirk Hachenberger, The dynamics of linearized polynomials, Proc. Edinburgh Math. Soc. (2) 43 (2000), no. 1, 113–128. MR 1744703, https://doi.org/10.1017/S0013091500020733
- 10. 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
- 11. 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.
- 12. P. Deligne, `Applications de la formule des traces aux sommes trigonométriques', Lect. Notes in Mathematics, Springer-Verlag, Berlin, 569 (1977), 168-232.
- 13. Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456
- 14. Graham Everest and Thomas Ward, Heights of polynomials and entropy in algebraic dynamics, Universitext, Springer-Verlag London, Ltd., London, 1999. MR 1700272
- 15. Sergey Fomin and Andrei Zelevinsky, The Laurent phenomenon, Adv. in Appl. Math. 28 (2002), no. 2, 119–144. MR 1888840, https://doi.org/10.1006/aama.2001.0770
- 16. 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, https://doi.org/10.1112/S0025579300015734
- 17. 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, https://doi.org/10.1090/S0025-5718-00-01282-5
- 18. John B. Friedlander and Igor E. Shparlinski, On the distribution of the power generator, Math. Comp. 70 (2001), no. 236, 1575–1589. MR 1836920, https://doi.org/10.1090/S0025-5718-00-01283-7
- 19. 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, https://doi.org/10.1137/0217016
- 20. 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, https://doi.org/10.1007/3-540-46796-3_9
- 21. Domingo Gómez, Jaime Gutierrez, and Álvar Ibeas, Attacking the Pollard generator, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5518–5523. MR 2300710, https://doi.org/10.1109/TIT.2006.885451
- 22. 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, https://doi.org/10.1007/3-540-45624-4_20
- 23. 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, https://doi.org/10.1016/j.ffa.2004.08.001
- 24. 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, https://doi.org/10.1007/s10623-007-9112-3
- 25. 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, https://doi.org/10.1016/j.ffa.2007.03.004
- 26. 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, https://doi.org/10.1112/jlms/jdn034
- 27. Antoine Joux and Jacques Stern, Lattice reduction: a toolbox for the cryptanalyst, J. Cryptology 11 (1998), no. 3, 161–185. MR 1633944, https://doi.org/10.1007/s001459900042
- 28. Nicholas M. Katz, Estimates for “singular” exponential sums, Internat. Math. Res. Notices 16 (1999), 875–899. MR 1715519, https://doi.org/10.1155/S1073792899000458
- 29. Hugo Krawczyk, How to predict congruential generators, J. Algorithms 13 (1992), no. 4, 527–545. MR 1187200, https://doi.org/10.1016/0196-6774(92)90054-G
- 30. L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR 0419394
- 31. 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, https://doi.org/10.1090/psapm/042/1095554
- 32. 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
- 33. 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, https://doi.org/10.24033/bsmf.2441
- 34. Greg Martin and Carl Pomerance, The iterated Carmichael 𝜆-function and the number of cycles of the power generator, Acta Arith. 118 (2005), no. 4, 305–335. MR 2165548, https://doi.org/10.4064/aa118-4-1
- 35. Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447, https://doi.org/10.1090/S0002-9904-1978-14532-7
- 36. 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
- 37. 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, https://doi.org/10.1006/ffta.1999.0257
- 38. 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, https://doi.org/10.1090/S0025-5718-00-01273-4
- 39. 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
- 40. 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, https://doi.org/10.1007/3-540-44828-4_2
- 41. Harald Niederreiter and Arne Winterhof, Exponential sums for nonlinear recurring sequences, Finite Fields Appl. 14 (2008), no. 1, 59–64. MR 2381476, https://doi.org/10.1016/j.ffa.2006.09.010
- 42. 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, https://doi.org/10.3934/dcds.2007.17.901
- 43. Joseph H. Silverman, The arithmetic of dynamical systems, Graduate Texts in Mathematics, vol. 241, Springer, New York, 2007. MR 2316407
- 44. Joseph H. Silverman, Variation of periods modulo 𝑝 in arithmetic dynamics, New York J. Math. 14 (2008), 601–616. MR 2448661
- 45. 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, https://doi.org/10.1007/1-4020-5334-4_4
- 46. Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over 𝐺𝐹(𝑝), Discrete Math. 277 (2004), no. 1-3, 219–240. MR 2033734, https://doi.org/10.1016/S0012-365X(03)00158-4
Retrieve articles in Mathematics of Computation with MSC (2000): 11K45, 11T23, 37A45, 37F10
Retrieve articles in all journals with MSC (2000): 11K45, 11T23, 37A45, 37F10
Additional Information
Alina Ostafe
Affiliation:
Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190 CH-8057, Zürich, Switzerland
Email:
alina.ostafe@math.uzh.ch
Igor E. Shparlinski
Affiliation:
Department of Computing, Macquarie University, NSW 2109, Australia
Email:
igor@ics.mq.edu.au
DOI:
https://doi.org/10.1090/S0025-5718-09-02271-6
Received by editor(s):
February 23, 2009
Received by editor(s) in revised form:
March 9, 2009
Published electronically:
July 7, 2009
Article copyright:
© Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.