Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Algebraic entropy, automorphisms and sparsity of algebraic dynamical systems and pseudorandom number generators


Authors: Domingo Gómez-Pérez, Alina Ostafe and Igor Shparlinski
Journal: Math. Comp. 83 (2014), 1535-1550
MSC (2010): Primary 11K45, 37A45; Secondary 11T71, 65C10, 94A60
DOI: https://doi.org/10.1090/S0025-5718-2013-02780-9
Published electronically: September 30, 2013
MathSciNet review: 3167471
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present several general results that show how algebraic dynamical systems with a slow degree growth and also rational automorphisms can be used to construct stronger pseudorandom number generators. We then give several concrete constructions that illustrate the applicability of these general results.


References [Enhancements On Off] (What's this?)

  • [1] M. P. Bellon and C.-M. Viallet, Algebraic entropy, Comm. Math. Phys. 204 (1999), no. 2, 425-437. MR 1704282 (2000f:37040), https://doi.org/10.1007/s002200050652
  • [2] Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456 (98j:11057)
  • [3] 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 (2003g:11089), https://doi.org/10.1112/S0025579300015734
  • [4] Carlos J. Moreno and Oscar Moreno, Exponential sums and Goppa codes. I, Proc. Amer. Math. Soc. 111 (1991), no. 2, 523-531. MR 1028291 (91f:11087), https://doi.org/10.2307/2048345
  • [5] Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957-1041. MR 508447 (80d:65016), https://doi.org/10.1090/S0002-9904-1978-14532-7
  • [6] 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 (93h:65008)
  • [7] 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 (electronic). MR 1836919 (2002e:11104), https://doi.org/10.1090/S0025-5718-00-01273-4
  • [8] 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 (2003g:11085)
  • [9] Harald Niederreiter and Igor E. Shparlinski, Dynamical systems generated by rational functions, (Toulouse, 2003) Lecture Notes in Comput. Sci., vol. 2643, Springer, Berlin, 2003, pp. 6-17. MR 2042407 (2005a:94047), https://doi.org/10.1007/3-540-44828-4_2
  • [10] Harald Niederreiter and Arne Winterhof, Exponential sums for nonlinear recurring sequences, Finite Fields Appl. 14 (2008), no. 1, 59-64. MR 2381476 (2008m:11166), https://doi.org/10.1016/j.ffa.2006.09.010
  • [11] Alina Ostafe, Multivariate permutation polynomial systems and nonlinear pseudorandom number generators, Finite Fields Appl. 16 (2010), no. 3, 144-154. MR 2610705 (2011d:65014), https://doi.org/10.1016/j.ffa.2009.12.003
  • [12] Alina Ostafe, Pseudorandom vector sequences of maximal period generated by triangular polynomial dynamical systems, Des. Codes Cryptogr. 63 (2012), no. 1, 59-72. MR 2890322, https://doi.org/10.1007/s10623-011-9535-8
  • [13] Alina Ostafe and Igor E. Shparlinski, On the degree growth in some polynomial dynamical systems and nonlinear pseudorandom number generators, Math. Comp. 79 (2010), no. 269, 501-511. MR 2552237 (2010i:11120), https://doi.org/10.1090/S0025-5718-09-02271-6
  • [14] Alina Ostafe and Igor E. Shparlinski, Pseudorandom numbers and hash functions from iterations of multivariate polynomials, Cryptogr. Commun. 2 (2010), no. 1, 49-67. MR 2592430 (2011a:11144), https://doi.org/10.1007/s12095-009-0016-0
  • [15] Alina Ostafe and Igor E. Shparlinski, On the power generator and its multivariate analogue, J. Complexity 28 (2012), no. 2, 238-249. MR 2900832, https://doi.org/10.1016/j.jco.2011.10.010
  • [16] Alina Ostafe and Igor Shparlinski, Degree growth, linear independence and periods of a class of rational dynamical systems, Arithmetic, geometry, cryptography and coding theory, Contemp. Math., vol. 574, Amer. Math. Soc., Providence, RI, 2012, pp. 131-143. MR 2961405, https://doi.org/10.1090/conm/574/11426
  • [17] Alina Ostafe, Igor E. Shparlinski, and Arne Winterhof, On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences, Adv. Math. Commun. 4 (2010), no. 3, 369-379. MR 2677868 (2011i:65009), https://doi.org/10.3934/amc.2010.4.369
  • [18] 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 (2007j:11098), https://doi.org/10.3934/dcds.2007.17.901
  • [19] 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 (2007m:11106), https://doi.org/10.1007/1-4020-5334-4_4
  • [20] Tuyen Trung Truong, Degree complexity of a family of birational maps. II. Exceptional cases, Math. Phys. Anal. Geom. 12 (2009), no. 2, 157-180. MR 2497321 (2010c:32031), https://doi.org/10.1007/s11040-009-9057-z
  • [21] C.-M. Viallet, Algebraic dynamics and algebraic entropy, Int. J. Geom. Methods Mod. Phys. 5 (2008), no. 8, 1373-1391. MR 2484559 (2009m:37011), https://doi.org/10.1142/S0219887808003375
  • [22] Arne Winterhof, Recent results on recursive nonlinear pseudorandom number generators (invited paper), Sequences and their applications--SETA 2010, Lecture Notes in Comput. Sci., vol. 6338, Springer, Berlin, 2010, pp. 113-124. MR 2830717 (2012m:11103), https://doi.org/10.1007/978-3-642-15874-2_9

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11K45, 37A45, 11T71, 65C10, 94A60

Retrieve articles in all journals with MSC (2010): 11K45, 37A45, 11T71, 65C10, 94A60


Additional Information

Domingo Gómez-Pérez
Affiliation: Department of Mathematics, University of Cantabria, Santander 39005, Spain
Email: domingo.gomez@unican.es

Alina Ostafe
Affiliation: Department of Computing, Macquarie University, Sydney NSW 2109, Australia
Email: alina.ostafe@mq.edu.au

Igor Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney NSW 2109, Australia
Address at time of publication: Department of Pure Mathematics, University of New South Wales, Sydney, \indent NSW 2052, Australia
Email: igor.shparlinski@unsw.edu.au

DOI: https://doi.org/10.1090/S0025-5718-2013-02780-9
Keywords: Pseudorandom numbers, polynomial iterations
Received by editor(s): May 19, 2012
Received by editor(s) in revised form: October 2, 2012, and November 16, 2012
Published electronically: September 30, 2013
Article copyright: © Copyright 2013 American Mathematical Society

American Mathematical Society