Изучаются вероятностные характеристики графа случайного отображения f[k] - композиции k независимых равновероятных случайных отображений f1,.....,fk, где fi: {1,...,n} → {1,...,n}, n,k ∈ ℕ, i = 1,...,n. Получены формулы для распределения длины отрезка апериодичности произвольной вершины в графе отображения f[k] с учётом ряда ограничений. Выписаны формулы для вероятностей принадлежности вершины множеству f[k] ({1,..., n}) и множеству висячих вершин в графе отображения f[k]. Вычислены вероятности инцидентности двух произвольных вершин одной компоненте связности, попадания произвольной вершины в множество прообразов другой вершины, а также появления коллизии в указанном графе.
Скачать электронную версию публикации
Загружен, раз: 95
- Title Об образах и прообразах в графе композиции независимых равновероятных случайных отображений
- Headline Об образах и прообразах в графе композиции независимых равновероятных случайных отображений
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 49
- Date:
- DOI 10.17223/20710410/49/1
Ключевые слова
равновероятное случайное отображение, композиция отображений, граф отображения, образ множества, прообраз вершины, висячая вершина, слой в графе, отрезок апериодичности, коллизия, equiprobable random mapping, composition of mappings, graph of a mapping, image of a multitude, pre-image of a vertex, initial vertex, layer in a graph, aperiodicity segment, collisionАвторы
Ссылки
Миронкин В. О. Распределение длины отрезка апериодичности в графе композиции независимых равновероятных случайных отображений // Математические вопросы криптографии. 2019. Т. 10. №3. С. 89-99.
Миронкин В. О. Слои в графе композиции независимых равновероятных случайных отображений // Математические вопросы криптографии. 2020. Т. 11. №1. С. 101-114.
Зубков А. М., Серов А. А. Предельная теорема для мощности образа подмножества при композиции случайных отображений // Дискретная математика. 2017. Т. 29. №1. С.17-26.
Зубков А. М., Серов А. А. Оценки среднего размера образа подмножества при композиции случайных отображений // Дискретная математика. 2018. Т. 30. №2. С. 27-36.
Серов А. А. Образы конечного множества при итерациях двух случайных зависимых отображений // Дискретная математика. 2015. Т. 27. №4. С. 133-140.
Dalal A. and Schmutz E. Compositions of random functions on a finite set // Electr. J. Comb. 2002. V. 9. No. R26. P. 1-7.
Fill J. A. On compositions of random functions on a finite set // 2002. P. 1-15. http://www. mts.jhu.edu/~fill/
Миронкин В. О. О некоторых вероятностных характеристиках алгоритма выработки ключа “CRYPTOPRO KEY MESHING” // Проблемы информационной безопасности. Компьютерные системы. 2015. №4. С. 140-146.
Ahmetzyanova L. R., Alekseev E. K., Oshkin I. B., et al. On the properties of the CTR encryption mode of Magma and Kuznyechik block ciphers with re-keying method based on CryptoPro Key Meshing // Математические вопросы криптографии. 2017. Т. 8. №2. С. 39-50.
Колчин В. Ф. Случайные отображения. М.: Наука, 1984. 208с.
Сачков В. Н. Вероятностные методы в комбинаторном анализе. М.: Наука, 1978. 288с.
Harris B. Probability distributions related to random mapping // Ann. Math. Statist. 1960. V.31. No. 4. P.1045-1062.
Flajolet P. and Odlyzko A. Random mapping statistics // LNCS. 1989. V. 434. P.329-354.
Колчин В. Ф., Севастьянов Б. А., Чистяков В. П. Случайные размещения. М.: Наука, 1976. 224 с.
Об образах и прообразах в графе композиции независимых равновероятных случайных отображений | Прикладная дискретная математика. 2020. № 49. DOI: 10.17223/20710410/49/1
Скачать полнотекстовую версию
Загружен, раз: 190