Geodesic
Distribution of the length of aperiodicity segment in the graph of $k$-fold iteration of uniform random mapping
Matematičeskie voprosy kriptografii, Tome 8 (2017), pp. 63-74.

Voir la notice de l'article provenant de la source Math-Net.Ru

The distribution of the length of the aperiodicity segment in a graph of $k$-fold iteration of random uniform mapping of a finite set is studied. Exact formulas for this distribution are obtained, the limit distribution of the normed length of aperiodicity segment is found for the case when the cardinality of the set tends to infinity. 
@article{MVK_2017_8_a2,
     author = {A. M. Zubkov and V. O. Mironkin},
     title = {Distribution of the length of aperiodicity segment in the graph of $k$-fold iteration of uniform random mapping},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {63--74},
     publisher = {mathdoc},
     volume = {8},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2017_8_a2/}
}
TY  - JOUR
AU  - A. M. Zubkov
AU  - V. O. Mironkin
TI  - Distribution of the length of aperiodicity segment in the graph of $k$-fold iteration of uniform random mapping
JO  - Matematičeskie voprosy kriptografii
PY  - 2017
SP  - 63
EP  - 74
VL  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MVK_2017_8_a2/
LA  - ru
ID  - MVK_2017_8_a2
ER  - 
%0 Journal Article
%A A. M. Zubkov
%A V. O. Mironkin
%T Distribution of the length of aperiodicity segment in the graph of $k$-fold iteration of uniform random mapping
%J Matematičeskie voprosy kriptografii
%D 2017
%P 63-74
%V 8
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MVK_2017_8_a2/
%G ru
%F MVK_2017_8_a2
A. M. Zubkov; V. O. Mironkin. Distribution of the length of aperiodicity segment in the graph of $k$-fold iteration of uniform random mapping. Matematičeskie voprosy kriptografii, Tome 8 (2017), pp. 63-74. http://geodesic.mathdoc.fr/item/MVK_2017_8_a2/

[1] Kolchin V. F., Sluchainye otobrazheniya, Nauka, M., 1984

[2] Zubkov A. M., “Vychislenie raspredeleniya kharakteristik chisla komponent i tsiklicheskikh tochek sluchainogo otobrazheniya”, Matematicheskie voprosy kriptografii, 1:2 (2010), 5–18

[3] Mironkin V. O., “Issledovanie svoistv i kharakteristik stepeni sluchainogo otobrazheniya”, Obozrenie prikl. i promyshl. matem., 21:1 (2014), 70–73

[4] Mironkin V. O., “Ob osobennostyakh stroeniya grafa stepeni sluchainogo otobrazheniya”, Obozrenie prikl. i promyshl. matem., 23:1 (2016), 57–62 | Zbl

[5] Sachkov V. N., Veroyatnostnye metody v kombinatornom analize, Nauka, M., 1978

[6] Stepanov V. E., “Predelnye raspredeleniya nekotorykh kharakteristik sluchainykh otobrazhenii”, Teoriya veroyatn. i ee primen., 14:4 (1969), 639–653

[7] Tokareva N. N., Simmetrichnaya kriptografiya, Kratkii kurs: uchebnoe posobie, Novosib. gos. un-t, Novosibirsk, 2012, 234 pp.

[8] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, 2-e izd., Mir, M., 1964

[9] Flajolet P., Odlyzko A., “Random mapping statistics”, Lect. Notes Comput. Sci., 434, 1989, 329–354 | DOI | MR

[10] Harris B., “Probability distributions related to random mapping”, Ann. Math. Statist., 31:4 (1960), 1045–1062 | DOI | MR | Zbl

[11] Dalal A., Schmutz E., “Compositions of random functions on a finite set”, Electr. J. Comb., 9 (2002), R26 | MR | Zbl

[12] Goh W. M. Y., Hitczenko P., Schmutz E., Iterating random functions on a finite set, 2012, 7 pp., arXiv: math/0207276v2

[13] Kingman J. F. C., “The coalescent”, Stoch. Proc. Appl., 13 (235–248), 1982 | MR | Zbl

[14] McSweeney J. K., Pittel B. G., “Expected coalescence time for a nonuniform allocation process”, Adv. Appl. Probab., 40:4 (2008), 1002–1032 | DOI | MR | Zbl

[15] Hellman M. E., “A cryptanalytic time-memory trade-off”, IEEE Trans. Inf. Theory, 1980, 401–406 | DOI | MR | Zbl

[16] Hong J., Ma D., “Success probability of the Hellman trade-off”, Inf. Process. Lett., 109:7 (2009), 347–351 | DOI | MR | Zbl

[17] Oechslin P., “Making a faster cryptanalytic time-memory trade-off”, Lect. Notes Comput. Sci., 2729, 2003, 617–630 | DOI | MR | Zbl

[18] Pilshchikov D. V., “Estimation of the characteristics of time-memory-data tradeoff methods via generating functions of the number of particles and the total number of particles in the Galton–Watson process”, Matematicheskie voprosy kriptografii, 5:2 (2014), 103–108

[19] Pilshchikov D. V., “On the limiting mean values in probabilistic models of time-memory-data tradeoff methods”, Matematicheskie voprosy kriptografii, 6:2 (2015), 59–65 | MR

[20] Pilschikov D. V., “Asimptoticheskoe povedenie moschnosti polnogo proobraza sluchainogo mnozhestva pri iteratsiyakh otobrazhenii konechnogo mnozhestva”, Matematicheskie voprosy kriptografii, 8:1 (2017), 95–106

[21] Mironkin V. O., “O nekotorykh veroyatnostnykh kharakteristikakh algoritma vyrabotki klyucha «CRYPTOPRO KEY MESHING»”, Problemy informatsionnoi bezopasnosti. Kompyuternye sistemy, 2015, no. 4, 140–146

[22] Zubkov A. M., Serov A. A., “Sovokupnost obrazov podmnozhestva konechnogo mnozhestva pri iteratsiyakh sluchainykh otobrazhenii”, Diskretnaya matematika, 26:4 (2014), 43–50 | DOI

[23] Serov A. A., “Obrazy konechnogo mnozhestva pri iteratsiyakh dvukh sluchainykh zavisimykh otobrazhenii”, Diskretnaya matematika, 27:4 (2015), 133–140 | DOI

[24] Zubkov A. M., Serov A. A., “Predelnaya teorema dlya moschnosti obraza podmnozhestva pri kompozitsii sluchainykh otobrazhenii”, Diskretnaya matematika, 29:1 (2017), 17–26 | DOI