Том 27, номер 2, 2020 г., Стр. 117-135

УДК 519.17
Фомичёв В. М., Авезова Я. Э.
Точная формула экспонентов перемешивающих орграфов регистровых преобразований

Аннотация:
Орграф называется примитивным, если его некоторая степень есть полный орграф (содержит все возможные дуги), а наименьшее такая степень называется экспонентом орграфа. В примитивном орграфе элементарным локальным экспонентом для вершин $u$ и $v$ называют наименьшее целое положительное $\gamma$ такое, что в орграфе есть пути из $u$ в $v$ любой длины, не меньшей $\gamma$. Преобразованию двоичного $n$-мерного векторного пространства, заданному системой $n$ координатных функций, соответствует $n$-вершинный ориентированный граф, где пара ($u, v$) есть дуга, если координатная функция с номером $v$ зависит существенно от переменной с номером $u$. Такой орграф называют перемешивающим графом преобразования. Исследованы перемешивающие графы широко используемых в криптологии преобразований регистров сдвига длины $n > 1$ с нелинейной булевой функцией обратной связи. Получена точная формула экспонента и элементарных локальных экспонентов для примитивного перемешивающего орграфа преобразования регистра сдвига. Результаты могут применяться для оценки длины холостого хода генераторов псевдослучайных последовательностей.
Библиогр. 20.

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

DOI: 10.33048/daio.2020.27.670

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

Статья поступила 6 сентября 2019 г.
После доработки — 27 сентября 2019 г.
Принята к публикации 19 февраля 2020 г.

Литература

[1] Frobenius G. Über Matrizen aus nicht negativen Elementen // Berl. Ber. 1912. P. 456–477.

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

[3] Фомичёв В. М., Авезова Я. Э., Коренева А. М., Кяжин С. Н. Примитивность и локальная примитивность орграфов и неотрицательных матриц // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 3. С. 95–125.

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

[5] Протасов В. Ю. Полугруппы неотрицательных матриц // Успехи мат. наук. 2010. Т. 65, вып. 6. С. 191–192.

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

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

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

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

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

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

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

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

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

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

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

[17] Фомичёв В. М. Об улучшенной универсальной оценке экспонентов ор- графов // Прикл. дискрет. математика. 2019. № 43. С. 115–123.

[18] Golomb S. W. Shift register sequences — a retrospective account // Sequences and Their Appl. Proc. 4th Int. Conf. (Beijing, China, Sept. 24–28, 2006). Heidelberg: Springer, 2012. P. 1–4 (Lect. Notes Comput. Sci.; Vol. 4086).

[19] Goresky M., Klapper A. Algebraic shift register sequences. Cambridge: Camb. Univ. Press, 2012. 514 p.

[20] Солодовников В. И. Регистры сдвига и криптоалгоритмы на их основе. Lambert Acad. Publ., 2017. 112 с.