Iteration entropy

von zur Gathen, Joachim

doi:10.1090/mcom/3382

Iteration entropy

Author: Joachim von zur Gathen
Journal: Math. Comp. 88 (2019), 1991-2003
MSC (2010): Primary 11K45, 37P25, 68W20, 94A60
DOI: https://doi.org/10.1090/mcom/3382
Published electronically: October 30, 2018
MathSciNet review: 3925494
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: We apply a common measure of randomness, the entropy, in the context of iterated functions on a finite set with elements. For a permutation, this entropy turns out to be asymptotically (for a growing number of iterations) close to $\log _2 n$ minus the entropy of the vector of its cycle lengths. For general functions, a similar approximation holds.

[1] Richard Arratia and Simon Tavaré, The cycle structure of random permutations, Ann. Probab. 20 (1992), no. 3, 1567–1591. MR 1175278
[2] Richard Arratia, A. D. Barbour, and Simon Tavaré, On random polynomials over finite fields, Math. Proc. Cambridge Philos. Soc. 114 (1993), no. 2, 347–368. MR 1230136, https://doi.org/10.1017/S0305004100071620
[3] Elisa Bellah, Derek Garton, Erin Tannenbaum, and Noah Walton, A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields, Involve 11 (2018), no. 1, 169–179. MR 3681355, https://doi.org/10.2140/involve.2018.11.169
[4] L. Blum, M. Blum, and M. Shub, A simple unpredictable pseudorandom number generator, SIAM J. Comput. 15 (1986), no. 2, 364–383. MR 837589, https://doi.org/10.1137/0215025
[5] L. Boppré, J. von zur Gathen, L. Perin, and A. Zumalacárregui,
Sidon sets and statistics of the ElGamal function, 2017.
Preprint, https://arxiv.org/abs/1708.04395.
[6] Joan Boyar, Inferring sequences produced by pseudo-random number generators, J. Assoc. Comput. Mach. 36 (1989), no. 1, 129–141. MR 1072416, https://doi.org/10.1145/58562.59305
[7] Andrew Bridy and Derek Garton, Dynamically distinguishing polynomials, Res. Math. Sci. 4 (2017), Paper No. 13, 17. MR 3669394, https://doi.org/10.1186/s40687-017-0103-3
[8] Charles Burnette and Eric Schmutz, Periods of iterated rational functions, Int. J. Number Theory 13 (2017), no. 5, 1301–1315. MR 3639698, https://doi.org/10.1142/S1793042117500713
[9] 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
[10] Philippe Flajolet and Andrew M. Odlyzko, Random mapping statistics, Advances in cryptology—EUROCRYPT ’89 (Houthalen, 1989) Lecture Notes in Comput. Sci., vol. 434, Springer, Berlin, 1990, pp. 329–354. MR 1083961, https://doi.org/10.1007/3-540-46885-4_34
[11] Ryan Flynn and Derek Garton, Graph components and dynamics over finite fields, Int. J. Number Theory 10 (2014), no. 3, 779–792. MR 3190008, https://doi.org/10.1142/S1793042113501224
[12] 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
[13] Dennis Hofheinz, Eike Kiltz, and Victor Shoup, Practical chosen ciphertext secure encryption from factoring, J. Cryptology 26 (2013), no. 1, 102–118. MR 3016825, https://doi.org/10.1007/s00145-011-9115-0
[14] Sergei V. Konyagin, Florian Luca, Bernard Mans, Luke Mathieson, Min Sha, and Igor E. Shparlinski, Functional graphs of polynomials over finite fields, J. Combin. Theory Ser. B 116 (2016), 87–122. MR 3425238, https://doi.org/10.1016/j.jctb.2015.07.003
[15] Pär Kurlberg and Carl Pomerance, On the periods of the linear congruential and power generators, Acta Arith. 119 (2005), no. 2, 149–169. MR 2167719, https://doi.org/10.4064/aa119-2-2
[16] G. Lasry,
A Methodology for the Cryptanalysis of Classical Ciphers with Search Metaheuristics,
Universität Kassel, Germany, 2017,
Ph.D. Thesis.
[17] B. Mans, M. Sha, I. E. Shparlinski, and D. Sutantyo,
On functional graphs of quadratic polynomials, 2017,
arXiv:1706.04734, to appear in Experimental Mathematics.
[18] Rodrigo S. V. Martins and Daniel Panario, On the heuristic of approximating polynomials over finite fields by random mappings, Int. J. Number Theory 12 (2016), no. 7, 1987–2016. MR 3544423, https://doi.org/10.1142/S1793042116501219
[19] R. S. V. Martins, D. Panario, C. Qureshi, and E. Schmutz,
Periods of iterations of mappings over finite fields with restricted preimage sizes,
AofA 2018, LIPIC (Leibniz International Proceedings in Informatics), Vol. 110, Dagstuhl Publishing, 2018.
arXiv:1701.09148
[20] Alina Ostafe and Min Sha, Counting dynamical systems over finite fields, Dynamics and numbers, Contemp. Math., vol. 669, Amer. Math. Soc., Providence, RI, 2016, pp. 187–203. MR 3546669, https://doi.org/10.1090/conm/669/13429
[21] Carl Pomerance and Igor E. Shparlinski, Connected components of the graph generated by power maps in prime finite fields, Integers 18A (2018), Paper No. A16, 8. MR 3777538
[22] Min Sha, On the cycle structure of repeated exponentiation modulo a prime power, Fibonacci Quart. 49 (2011), no. 4, 340–347. MR 2852007
[23] Min Sha and Su Hu, Monomial dynamical systems of dimension one over finite fields, Acta Arith. 148 (2011), no. 4, 309–331. MR 2800698, https://doi.org/10.4064/aa148-4-1
[24] L. A. Shepp and S. P. Lloyd, Ordered cycle lengths in a random permutation, Trans. Amer. Math. Soc. 121 (1966), 340–357. MR 195117, https://doi.org/10.1090/S0002-9947-1966-0195117-8
[25] Abraham Sinkov, Elementary cryptanalysis, 2nd ed., Anneli Lax New Mathematical Library, vol. 22, Mathematical Association of America, Washington, DC, 2009. A mathematical approach; Revised, updated and with a preface by Todd Feil. MR 2530836
[26] 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