Iteration entropy

von zur Gathen, Joachim

doi:10.1090/mcom/3382

Iteration entropy
HTML articles powered by AMS MathViewer

by Joachim von zur Gathen HTML | PDF

Math. Comp. 88 (2019), 1991-2003 Request permission

Abstract:

We apply a common measure of randomness, the entropy, in the context of iterated functions on a finite set with $n$ 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.

References

Richard Arratia and Simon Tavaré, The cycle structure of random permutations, Ann. Probab. 20 (1992), no. 3, 1567–1591. MR 1175278
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, DOI 10.1017/S0305004100071620
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, DOI 10.2140/involve.2018.11.169
L. Blum, M. Blum, and M. Shub, A simple unpredictable pseudorandom number generator, SIAM J. Comput. 15 (1986), no. 2, 364–383. MR 837589, DOI 10.1137/0215025
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.
Joan Boyar, Inferring sequences produced by pseudo-random number generators, J. Assoc. Comput. Mach. 36 (1989), no. 1, 129–141. MR 1072416, DOI 10.1145/58562.59305
Andrew Bridy and Derek Garton, Dynamically distinguishing polynomials, Res. Math. Sci. 4 (2017), Paper No. 13, 17. MR 3669394, DOI 10.1186/s40687-017-0103-3
Charles Burnette and Eric Schmutz, Periods of iterated rational functions, Int. J. Number Theory 13 (2017), no. 5, 1301–1315. MR 3639698, DOI 10.1142/S1793042117500713
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
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, DOI 10.1007/3-540-46885-4_{3}4
Ryan Flynn and Derek Garton, Graph components and dynamics over finite fields, Int. J. Number Theory 10 (2014), no. 3, 779–792. MR 3190008, DOI 10.1142/S1793042113501224
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
Dennis Hofheinz, Eike Kiltz, and Victor Shoup, Practical chosen ciphertext secure encryption from factoring, J. Cryptology 26 (2013), no. 1, 102–118. MR 3016825, DOI 10.1007/s00145-011-9115-0
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, DOI 10.1016/j.jctb.2015.07.003
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, DOI 10.4064/aa119-2-2
G. Lasry, A Methodology for the Cryptanalysis of Classical Ciphers with Search Metaheuristics, Universität Kassel, Germany, 2017, Ph.D. Thesis.
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.
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, DOI 10.1142/S1793042116501219
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
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, DOI 10.1090/conm/669/13429
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
Min Sha, On the cycle structure of repeated exponentiation modulo a prime power, Fibonacci Quart. 49 (2011), no. 4, 340–347. MR 2852007
Min Sha and Su Hu, Monomial dynamical systems of dimension one over finite fields, Acta Arith. 148 (2011), no. 4, 309–331. MR 2800698, DOI 10.4064/aa148-4-1
L. A. Shepp and S. P. Lloyd, Ordered cycle lengths in a random permutation, Trans. Amer. Math. Soc. 121 (1966), 340–357. MR 195117, DOI 10.1090/S0002-9947-1966-0195117-8
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
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