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