Geodesic
On the sets of images of $k$-fold iteration of uniform random mapping
Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 3, pp. 99-108 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The properties of the graph of $k$-fold iteration of uniform random mapping $f\colon \{1,\ldots,n\}\to \{1,\ldots,n\}$ are studied. Some recurrence formulas for the probabilities for a vertex to belong to the set of images $f^k(\{1,\ldots,n\})$ and to the set of the initial vertices in the graph of $f^k$ are obtained. 
@article{MVK_2018_9_3_a4,
     author = {V. O. Mironkin and V. G. Mikhailov},
     title = {On the sets of images of $k$-fold iteration of uniform random mapping},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {99--108},
     year = {2018},
     volume = {9},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2018_9_3_a4/}
}
TY  - JOUR
AU  - V. O. Mironkin
AU  - V. G. Mikhailov
TI  - On the sets of images of $k$-fold iteration of uniform random mapping
JO  - Matematičeskie voprosy kriptografii
PY  - 2018
SP  - 99
EP  - 108
VL  - 9
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MVK_2018_9_3_a4/
LA  - ru
ID  - MVK_2018_9_3_a4
ER  - 
%0 Journal Article
%A V. O. Mironkin
%A V. G. Mikhailov
%T On the sets of images of $k$-fold iteration of uniform random mapping
%J Matematičeskie voprosy kriptografii
%D 2018
%P 99-108
%V 9
%N 3
%U http://geodesic.mathdoc.fr/item/MVK_2018_9_3_a4/
%G ru
%F MVK_2018_9_3_a4
V. O. Mironkin; V. G. Mikhailov. On the sets of images of $k$-fold iteration of uniform random mapping. Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 3, pp. 99-108. http://geodesic.mathdoc.fr/item/MVK_2018_9_3_a4/

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

[2] Zubkov A. M., Mironkin V. O., “Raspredelenie dliny otrezka aperiodichnosti v grafe $k$-kratnoi iteratsii sluchainogo ravnoveroyatnogo otobrazheniya”, Matematicheskie voprosy kriptografii, 8:4 (2017), 63–74 | DOI

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

[4] Kolchin V. F., Sluchainye otobrazheniya, Nauka, M., 1984, 208 pp.

[5] Kolchin V. F., Sevastyanov B. A., Chistyakov V. P., Sluchainye razmescheniya, Nauka, M., 1976, 224 pp.

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

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

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

[9] Mikhailov V. G., “Issledovanie kombinatorno-veroyatnostnoi modeli avtomatov iz registrov s neravnomernym dvizheniem”, Trudy po diskretnoi matematike, 2002, 139–149

[10] Mikhailov V. G., “Issledovanie chisla tsiklicheskikh tochek avtomata iz registrov s neravnomernym dvizheniem”, Trudy po diskretnoi matematike, 2002, 167–172

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

[12] Pogorelov B. A., Sachkov V. N., Slovar kriptograficheskikh terminov, MTsNMO, M., 2006, 94 pp.

[13] Sachkov V. N., Veroyatnostnye metody v kombinatornom analize, Nauka, M., 1978, 288 pp.

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

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

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

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

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

[19] 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 | DOI

[20] 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 | DOI | MR