Mathematics of Computation

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

Author(s): Alina Ostafe; Igor E. Shparlinski.
Journal: Math. Comp. 79 (2010), 501-511.
MSC (2000): Primary 11K45, 11T23, 37A45, 37F10
Posted: July 7, 2009
Retrieve article in: PDF

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. Arnold, `The Fermat-Euler dynamical system and the statistics of the arithmetic of geometric progressions', Funct. Analysis Appl., 37 (2003), 1-15. MR 1988005 (2004k:11005)

2.

V. I. Arnold, `Number-theoretic turbulence in Fermat-Euler arithmetics and large Young diagrams geometry statistics', J. Math. Fluid Mech., 7 (2005), S4-S50. MR 2126128 (2006g:11199)

3.

V. I. Arnold, `Ergodic and arithmetical properties of geometrical progression's dynamics and of its orbits', Moscow Math. J., 5 (2005), 5-22. MR 2153464 (2006g:11200)

4.

S. R. Blackburn, D. Gomez-Perez, J. Gutierrez and I. E. Shparlinski, `Predicting the inversive generator', Lect. Notes in Comput. Sci., Springer-Verlag, Berlin, 2898 (2003), 264-275. MR 2090938 (2005e:94096)

5.

S. R. Blackburn, D. Gomez-Perez, J. Gutierrez and I. E. Shparlinski, `Predicting nonlinear pseudorandom number generators', Math. Comp., 74 (2005), 1471-1494. MR 2137013 (2005m:11142)

6.

J. Bourgain, `Mordell's exponential sum estimate revisited', J. Amer. Math. Soc., 18 (2005), 477-499. MR 2137982 (2006b:11099)

7.

M.-C. Chang, `On a problem of Arnold on uniform distribution', J. Funcional Analysis, 242 (2007), 272-280. MR 2274023 (2007j:37007)

8.

W.-S. Chou and I. E. Shparlinski, `On the cycle structure of repeated exponentiation modulo a prime', J. Number Theory, 107 (2004), 345-356. MR 2072394 (2005e:11118)

9.

S. D. Cohen and D. Hachenberger, `The dynamics of linearized polynomials', Proc. Edinburgh Math. Soc., 43 (2000), 113-128. MR 1744703 (2001a:11195)

10.

O. Colón-Reyes, A. S. Jarrah, R. Laubenbacher and B. Sturmfels, `Monomial dynamical systems over finite fields', Complex Systems, 16 (2006), 333-342. MR 2293353 (2007m:37041)

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.

M. Drmota and R. Tichy, Sequences, discrepancies and applications, Lect. Notes in Math. 1651, Springer-Verlag, Berlin, 1997. MR 1470456 (98j:11057)

14.

G. R. Everest and T. Ward, Heights of polynomials and entropy in algebraic dynamics, Springer-Verlag, London, 1999. MR 1700272 (2000e:11087)

15.

S. Fomin and A. Zelevinsky, `The Laurent phenomenon', Adv. in Appl. Math., 28 (2002), 119-144. MR 1888840 (2002m:05013)

16.

J. B. Friedlander, J. Hansen and I. E. Shparlinski, `On character sums with exponential functions', Mathematika, 47 (2000), 75-85. MR 1924489 (2003g:11089)

17.

J. B. Friedlander, C. Pomerance and I. E. Shparlinski, `Period of the power generator and small values of Carmichael's function', Math. Comp., 70 (2001), 1591-1605. MR 1836921 (2002g:11112)

18.

J. B. Friedlander and I. E. Shparlinski, `On the distribution of the power generator', Math. Comp., 70 (2001), 1575-1589. MR 1836920 (2002f:11107)

19.

A. M. Frieze, J. Håstad, R. Kannan, J. C. Lagarias and A. Shamir, `Reconstructing truncated integer variables satisfying linear congruences', SIAM J. Comp., 17 (1988), 262-280. MR 935340 (89d:11115)

20.

F. Griffin, H. Niederreiter and I. E. Shparlinski, `On the distribution of nonlinear recursive congruential pseudorandom numbers of higher orders', Lect. Notes in Comput. Sci., Springer-Verlag, Berlin, 1719 (1999), 87-93. MR 1846485 (2002j:94038)

21.

D. Gomez-Perez, J. Gutierrez and Á. Ibeas, `Attacking the Pollard generator', IEEE Trans. Inform. Theory, 52 (2006), 5518-5523.

MR 2300710 (2007m:94160)

22.

J. Gutierrez and D. Gomez-Perez, `Iterations of multivariate polynomials and discrepancy of pseudorandom numbers', Lect. Notes in Comput. Sci., Springer-Verlag, Berlin, 2227 (2001), 192-199. MR 1913465

23.

D. Gomez-Perez, J. Gutierrez and I. E, Shparlinski, `Exponential sums with Dickson polynomials', Finite Fields Appl., 12 (2006), 16-25. MR 2190184 (2006i:11144)

24.

J. Gutierrez and Á. Ibeas, `Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits', Designs, Codes and Cryptography, 41 (2007), 199-212. MR 2341883 (2008g:11204)

25.

J. Gutierrez and A. Winterhof, `Exponential sums of nonlinear congruential pseudorandom number generators with Rédei functions', Finite Fields Appl., 14 (2008), 410-416. MR 2401984 (2009b:11218)

26.

R. Jones, `The density of prime divisors in the arithmetic dynamics of quadratic polynomials', J. Lond. Math. Soc., 78 (2008), 523-544. MR 2439638

27.

A. Joux and J. Stern, `Lattice reduction: A toolbox for the cryptanalyst', J. Cryptology, 11 (1998), 161-185. MR 1633944 (99c:94031)

28.

N. Katz, `Estimates for ``singular'' exponential sums', International Mathematics Research Notices, 16 (1999), 875-899. MR 1715519 (2001d:11084)

29.

H. Krawczyk, `How to predict congruential generators', J. Algorithms, 13 (1992), 527-545. MR 1187200 (93g:65013)

30.

L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley-Interscience, New York-London-Sydney, 1974. MR 0419394 (54:7415)

31.

J. C. Lagarias, `Pseudorandom number generators in cryptography and number theory', Proc. Symp. in Appl. Math., Amer. Math. Soc., Providence, RI, 42 (1990), 115-143. MR 1095554 (92f:11109)

32.

R. Lidl and H. Niederreiter, Finite fields, Cambridge University Press, Cambridge, 1997. MR 1429394 (97i:11115)

33.

S. Marcello, `Sur la dynamique arithmétique des automorphismes de l'espace affine', Bull. Soc. Math. France, 131 (2003), 229-257. MR 1988948 (2004d:11053)

34.

G. Martin and C. Pomerance, `The iterated Carmichael $\lambda$ -function and the number of cycles of the power generator', Acta Arith., 118 (2005), 305-335. MR 2165548 (2006h:11119)

35.

H. Niederreiter, `Quasi-Monte Carlo methods and pseudo-random numbers', Bull. Amer. Math. Soc., 84 (1978), 957-1041. MR 508447 (80d:65016)

36.

H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM Press, 1992. MR 1172997 (93h:65008)

37.

H. Niederreiter and I. E. Shparlinski, `On the distribution and lattice structure of nonlinear congruential pseudorandom numbers', Finite Fields and Their Appl., 5 (1999), 246-253. MR 1702905 (2000i:11126)

38.

H. Niederreiter and I. E. Shparlinski, `On the distribution of inversive congruential pseudorandom numbers in parts of the period', Math. Comp., 70 (2001), 1569-1574. MR 1836919 (2002e:11104)

39.

H. Niederreiter and I. E. Shparlinski, `On the average distribution of inversive pseudorandom numbers', Finite Fields and Their Appl., 8 (2002), 491-503. MR 1933620 (2003g:11085)

40.

H. Niederreiter and I. E. Shparlinski, `Dynamical systems generated by rational functions', Lect. Notes in Comput. Sci., Springer-Verlag, Berlin, 2643 (2003), 6-17. MR 2042407 (2005a:94047)

41.

H. Niederreiter and A. Winterhof, `Exponential sums for nonlinear recurring sequences', Finite Fields Appl., 14 (2008), 59-64. MR 2381476 (2008m:11166)

42.

I. E. Shparlinski, `On some dynamical systems in finite fields and residue rings', Discr. and Cont. Dynam. Syst., Ser.A, 17 (2007), 901-917. MR 2276481 (2007j:11098)

43.

J. H. Silverman, The arithmetic of dynamical systems, Grad. Texts in Math. 241, Springer, New York, 2007. MR 2316407 (2008c:11002)

44.

J. H. Silverman, `Variation of periods modulo

in arithmetic dynamics', New York J. Math., 14 (2008), 601-616. MR 2448661

45.

A. Topuzoglu and A. Winterhof, `Pseudorandom sequences', Topics in Geometry, Coding Theory and Cryptography, Springer-Verlag, 2006, 135-166. MR 2278037 (2007m:11106)

46.

T. Vasiga and J. O. Shallit, `On the iteration of certain quadratic maps over ${\mathrm{GF}(p)}$ ', Discr. Math., 277 (2004), 219-240. MR 2033734 (2004k:05104)

Retrieve articles in Mathematics of Computation with MSC (2000): 11K45, 11T23, 37A45, 37F10

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: 10.1090/S0025-5718-09-02271-6
PII: S 0025-5718(09)02271-6
Received by editor(s): February 23, 2009
Received by editor(s) in revised form: March 9, 2009
Posted: July 7, 2009
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS