On the degree growth in some polynomial dynamical systems and nonlinear pseudorandom number generators

Ostafe, Alina; Shparlinski, Igor

doi:10.1090/S0025-5718-09-02271-6

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

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