Том 25, номер 3, 2018 г., Стр. 95-125

УДК 519.17
Фомичёв В. М., Авезова Я. Э., Коренева А. М., Кяжин С. Н.
Примитивность и локальная примитивность орграфов и неотрицательных матриц

Аннотация:
Дан обзор основных результатов исследования примитивности и локальной примитивности орграфов и матриц начиная с зарождения этого направления в 1912 г. по настоящее время. Представлены универсальные и частные критерии примитивности и локальной примитивности, универсальные и частные оценки экспонентов и локальных экспонентов орграфов и матриц. Описаны криптографические приложения данного математического аппарата для оценки перемешивающих свойств преобразований блочных шифров и генераторов гаммы. Сформулированы перспективные направления исследований в области примитивности и локальной примитивности орграфов и матриц.
Библиогр. 47.

Ключевые слова: примитивный орграф, примитивная матрица, локальная примитивность, примитивное множество, экспонент орграфа, экспонент матрицы, локальный экспонент орграфа.

DOI: 10.17377/daio.2018.25.595

Фомичёв Владимир Михайлович ^1,2,3
Авезова Яна Эдуардовна ²
Коренева Алиса Михайловна ²
Кяжин Сергей Николаевич ²
1. Финансовый университет при Правительстве Российской Федерации,
Ленинградский пр., 49, 125993 Москва, Россия
2. Национальный исследовательский ядерный университет «МИФИ»,
Каширское ш., 31, 115409 Москва, Россия
3. Институт проблем информатики ФИЦ ИУ РАН,
ул. Вавилова, 44, корп. 2, 119333 Москва, Россия
е-mail: fomichev@nm.ru, avezovayana@gmail.com, alisa.koreneva@gmail.com, s.kyazhin@kaf42.ru

Статья поступила 16 октября 2017 г.
Исправленный вариант — 23 марта 2018 г.

Литература

[1] Авезова Я. Э. О примитивности некоторых множеств перемешивающих орграфов регистровых преобразований // Прикл. дискрет. математика. Прил. 2017. № 10. С. 60–62.

[2] Авезова Я. Э., Фомичёв В. M. Комбинаторные свойства систем разноразмерных 0,1-матриц // Прикл. дискрет. математика. 2014. № 2 (24). С. 5–11.

[3] Авезова Я. Э., Фомичёв В. M. Условия примитивности и оценки экспонентов множеств ориентированных графов // Прикл. дискрет. математика. 2017. № 35. С. 89–101.

[4] Альпин Ю. А., Альпина В. С. Комбинаторные свойства неприводимых полугрупп неотрицательных матриц // Зап. научн. сем. ПОМИ. 2012. № 405. С. 13–23.

[5] Войнов А. С. Многомерные уравнения самоподобия и приложения: дисс. . . . докт. физ.-мат. наук: 01.01.01. Москва, 2016. 75 с.

[6] Дорохова А. М., Фомичёв В. M. Уточненные оценки экспонентов перемешивающих графов биективных регистров сдвига над множеством двоичных векторов // Прикл. дискрет. математика. 2014. № 1. С. 77–83.

[7] Князев А. В. Оценки экстремальных значений основных метрических характеристик псевдосимметрических графов: дисс. . . . докт. физ.-мат. наук: 01.01.09. Москва, 2002. 203 с.

[8] Коренева А. М., Фомичёв В. M. Перемешивающие свойства модифицированных аддитивных генераторов // Дискрет. анализ и исслед. операций. 2017. Т. 24, № 2. С. 32–52.

[9] Кяжин С. Н. О применении условий локальной примитивности и оценок локальных экспонентов орграфов // Прикл. дискрет. математика. 2016. № 4. С. 81–98.

[10] Кяжин С. Н., Фомичёв В. M. Локальная примитивность графов и неотрицательных матриц // Прикл. дискрет. математика. 2014. № 3. С. 68–80.

[11] Кяжин С. Н., Фомичёв В. M. О локальных экспонентах перемешивающих графов функций, реализуемых алгоритмами типа А5/1 // Прикл. дискрет. математика. Прил. 2015. № 8. С. 11–13.

[12] Кяжин С. Н., Фомичёв В. M. Перемешивающие свойства двухкаскадных генераторов // Прикл. дискрет. математика. Прил. 2016. № 9. С. 60–62.

[13] Сачков В. Н. Вероятностные преобразователи и правильные мультиграфы // Тр. по дискрет. математике. 1997. Т. 1. С. 227–250.

[14] Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000. 448 с.

[15] Фомичёв В. М. Методы дискретной математики в криптологии. М.: Диалог-МИФИ, 2010. 424 с.

[16] Фомичёв В. М. Свойства путей в графах и мультиграфах // Прикл. дискрет. математика. 2010. № 1. С. 118–124.

[17] Фомичёв В. М. Оценки экспонентов примитивных графов // Прикл. дискрет. математика. 2011. № 2. С. 101–112.

[18] Фомичёв В. М. Оценка экспонента некоторых графов с помощью чисел Фробениуса для трёх аргументов // Прикл. дискрет. математика. 2014. № 2. С. 88–96.

[19] Фомичёв В. М. Новая универсальная оценка экспонентов графов // Прикл. дискрет. математика. 2016. № 3. С. 78–84.

[20] Фомичёв В. М. О вычислительной сложности оригинальной и расширенной диофантовой проблемы Фробениуса // Дискрет. анализ и исслед. операций. 2017. Т. 24, № 3. С. 104–124.

[21] Фомичёв В. М., Кяжин С. Н. Локальная примитивность матриц и графов // Дискрет. анализ и исслед. операций. 2017. Т. 24, № 1. С. 97–119.

[22] Фомичёв В. М., Мельников Д. А. Криптографические методы защиты информации. М.: Изд-во ЮРАЙТ, 2016. 454 с.

[23] Anderson R. On Fibonacci keystream generators // Fast Software Encryption. Proc. 2nd Int. Workshop (Leuven Belgium, Dec. 14–16, 1994). Heidelberg: Springer, 1995. P. 346–352. (Lect. Notes Comput. Sci.; Vol. 1008).

[24] Barghi A. Exponents of primitive digraphs // https://math.dartmouth.edu/˜pw/M100W11/amir.pdf.

[25] Berger T. P., Francq J., Minier M., Thomas G. Extended generalized Feistel networks using matrix representation to propose a new lightweight block cipher: Lilliput // IEEE Trans. Comput. 2016. Vol. 65, No. 7. P. 2074–2089.

[26] Berger T. P., Minier M., Thomas G. Extended generalized Feistel networks using matrix representation // Selected Areas in Cryptography. Rev. Sel. Pap. 20th Int. Conf. (Burnaby, Canada, Aug. 14–16, 2013). Heidelberg: Springer, 2014. P. 289–305. (Lect. Notes Comput. Sci.; Vol. 8282).

[27] Blöcher U., Dichtl M. Fish: a fast software stream cipher // Fast Software Encryption. Proc. Camb. Security Workshop (Cambridge, UK, Dec. 9–11, 1993). Heidelberg: Springer, 1994. P. 41–44. (Lect. Notes Comput. Sci.; Vol. 809).

[28] Blondel V. D., Jungers R. M., Olshevsky A. On primitivity of sets of matrices // Automatica. 2015. Vol. 61. P. 80–88.

[29] Brualdi R. A., Liu B. Generalized exponents of primitive directed graphs // J. Graph Theory. 1990. No. 14. P. 483–499.

[30] Dulmage A. L., Mendelsohn N. S. The exponent of a primitive matrix // Can. Math. Bull. 1962. No. 5. P. 241–244.

[31] Dulmage A. L., Mendelsohn N. S. Gaps in the exponent set of primitive matrices // Ill. J. Math. 1964. No. 8. P. 642–656.

[32] Dulmage A. L., Mendelsohn N. S. Graphs and matrices // Graph Theory Theor. Phys. 1967. P. 167–229.

[33] Frobenius G. Über Matrizen aus nicht negativen Elementen // Sitzungsber K. Preuss. Akad. Wiss. 1912. P. 456–477.

[34] Holladay J. C., Varga R. S. On powers of non-negative matrices // Proc. Amer. Math. Soc. 1958. Vol. 9. P. 631.

[35] Huang Y., Liu B. Generalized $r$-exponents of primitive digraphs // Taiwan. J. Math. 2011. Vol. 15, No. 5. P. 1999–2012.

[36] Lewin M., Vitek Y. A system of gaps in the exponent set of primitive matrices // Ill. J. Math. 1981. Vol. 25, No. 1. P. 87–98.

[37] Liu B. Generalized exponents of Boolean matrices // Linear Algebra Appl. 2003. Vol. 373. P. 169–182.

[38] Miao Z., Zhang K. The local exponent sets of primitive digraphs // Linear Algebra Appl. 2000. Vol. 307. P. 15–33.

[39] Neufeld S. W. A diameter bound on the exponent of a primitive directed graph // Linear Algebra Appl. 1996. Vol. 245. P. 27–47.

[40] Perkins P. A theorem on regular graphs // Pac. J. Math. 1961. Vol. 2. P. 1529–1533.

[41] Protasov V. Yu., Voynov A. S. Sets of nonnegative matrices without positive products // Linear Algebra Appl. 2012. Vol. 437, No. 3. P. 749–765.

[42] Ramírez Alfonsín J. L. The Diophantine Frobenius problem // Oxford: Clarendon. Press, 2005. (Oxf. Lect. Ser. Math. Appl,; Vol. 30).

[43] Schneier B. Applied cryptography: protocols, algorithms, and source code in C. John Wiley & Sons, Inc., New York, 1996.

[44] Shen J., Neufeld S. Local exponents of primitive digraphs // Linear Algebra Appl. 1998. Vol. 268. P. 117–129.

[45] Suzaki T., Minematsu K. Improving the generalized Feistel // Fast Software Encryption. Rev. Sel. Pap. 17th Int. Workshop (Seoul, Korea, Feb. 7–10, 2010). Heidelberg: Springer, 2010. 2010. P. 19–39. (Lect. Notes Comput. Sci.; Vol. 6147).

[46] Voynov A. S. Shortest positive products of nonnegative matrices // Linear Algebra Appl. 2013. Vol. 439, No. 6. P. 1627–1634.

[47] Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Z. 1950. Bd. 52. S. 642–648.