Том 24, номер 1, 2017 г., Стр. 97-119

УДК 519.17
Фомичёв В. М., Кяжин С. Н.
Локальная примитивность матриц и графов

Аннотация:
Развивается матрично-графовый подход к оценке коммуникативных свойств системы взаимосвязанных объектов, применяемый, в частности, для исследования перемешивающих свойств итеративных криптографических преобразований двоичных векторных пространств, т. е. для исследования зависимости битов выходных блоков от входных битов. В ряде прикладных задач насыщенность связей объектов соответствует требуемому уровню, если положительна моделирующая связи матрица или её определённая подматрица (полным является моделирующий связи граф или его определённый подграф).
Введены понятия локальной примитивности и локальных экспонентов неотрицательной матрицы (графа), обобщающие и расширяющие область применения по сравнению с известными понятиями примитивности и экспонента. Получены универсальный критерий локальной примитивности орграфа и оценки локальных экспонентов, как универсальная оценка, так и её уточнения для различных частных случаев. Результаты применены для оценки перемешивающих свойств криптографического генератора, построенного на основе последовательного соединения двух регистров сдвига.
Табл. 2, библ. 12.

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

DOI: 10.17377/daio.2017.24.519

Фомичёв Владимир Михайлович ^1,2
Кяжин Сергей Николаевич ^2,3
1. Финансовый университет при Правительстве РФ,
Ленинградский пр., 49, 125993 Москва, Россия
2. Национальный исследовательский ядерный университет «МИФИ»,
Каширское шоссе, 31, 115409 Москва, Россия
3. Центр специальных разработок МО РФ,
ул. Свободы, 21, 125362 Москва, Россия
е-mail: fomichev@nm.ru, s.kyazhin@kaf42.ru

Статья поступила 7 декабря 2015 г.
Исправленный вариант — 9 июня 2016 г.

Литература

[1] Когос К. Г., Фомичёв В. М. Положительные свойства неотрицательных матриц // Прикл. дискрет. математика. 2012. № 4. С. 5–13.

[2] Кяжин С. Н., Фомичёв В. М. О примитивных наборах натуральных чисел // Прикл. дискрет. математика. 2012. № 2. С. 5–14.

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

[4] Окунев Л. Я. Краткий курс теории чисел. М.: Учпедгиз, 1956. 239 с.

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

[6] Alfonsin J. L. R. The Diophantine Frobenius problem. New York: Oxford Univ. Press, 2005. 243 p.

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

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

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

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

[11] Shao J.,Wang J., Li G. Generalized primitive exponents with the complete characterization of the extremal digraphs // Chinese J. Contemp. Math. 1994. Vol. 15, No. 4. P. 317—324.

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