Distribution of the length of aperiodicity segment in the graph of independent uniform random mappings composition

V. O. Mironkin

Matematičeskie voprosy kriptografii, Tome 10 (2019) no. 3, pp. 89-99

Résumé

We consider graph of independent uniform random mappings composition. The distribution of the length of aperiodicity segment in such graph is studied. Exact and asymptotic expressions as well as inequalities for the probability distribution, mathematical expectation of the length of aperiodicity segment, the number of vertices with aperiodicity segment of given length are obtained.

Bibliographie

[1] 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 | MR

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

[3] Mironkin V. O., “Ob otsenkakh raspredeleniya dliny otrezka aperiodichnosti v grafe $k$-kratnoi iteratsii ravnoveroyatnogo sluchainogo otobrazheniya”, Prikladnaya diskretnaya matematika, 42 (2018), 6–17 | MR

[4] Mironkin V. O., “Sloi v grafe $k$-kratnoi iteratsii ravnoveroyatnogo sluchainogo otobrazheniya”, Matematicheskie voprosy kriptografii, 10:1 (2019), 73–82 | DOI | MR

[5] Mironkin V. O., Mikhailov V. G., “O mnozhestve obrazov $k$-kratnoi iteratsii ravnoveroyatnogo sluchainogo otobrazheniya”, Matematicheskie voprosy kriptografii, 9:3 (2018), 99–108 | DOI | MR

[6] Mikhailov V. G., “O povtoryaemosti sostoyanii datchika psevdosluchainykh chisel pri ego mnogokratnom ispolzovanii”, Teoriya veroyatn. i ee primen., 40:4 (1995), 786–797 | MR | Zbl

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

[8] Pilschikov D. V., “Issledovanie slozhnosti metoda raduzhnykh tablits s markerami tsepochek”, Matematicheskie voprosy kriptografii, 8:4 (2017), 99–116 | DOI | MR

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

[10] Ahmetzyanova L. R., Alekseev E. K., Oshkin I. B., Smyshlyaev S. V., Sonina L. A., “On the properties of the CTR encryption mode of Magma and Kuznyechik block ciphers with re-keying method based on CryptoPro Key Meshing”, Matematicheskie voprosy kriptografii, 8:2 (2017), 39–50 | DOI | MR

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

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

[13] Zubkov A. M., Serov A. A., “Otsenki srednego razmera obraza podmnozhestva pri kompozitsii sluchainykh otobrazhenii”, Diskretnaya matematika, 30:2 (2018), 27–36 | DOI | Zbl

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

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

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

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

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

[21] 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

[22] Lagutin M. B., Naglyadnaya matematicheskaya statistika, uchebnoe posobie, 2-e izd., BINOM. Laboratoriya znanii, M., 2009, 472 pp.

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

[24] Vadzinskii R. N., Spravochnik po veroyatnostnym raspredeleniyam, Nauka, SPb., 2001, 295 pp.

[25] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, v. 2, Mir, M., 1984, 738 pp. | MR