Точная формула экспонента перемешивающего орграфа регистрового преобразования | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/8

Точная формула экспонента перемешивающего орграфа регистрового преобразования

Для примитивного перемешивающего n-вершинного орграфа Г (g) преобразования g двоичного регистра сдвига длины n, где обратная связь f (x0,..., xn-i) имеет m существенных переменных с множеством номеров D(g) = {di,..., dm}, n ^ 3, 2 ^ m ^ n, 0 = di <...< dm, при dm G {n - 1, n - 2} получена точная формула экспонента exp r(g) и элементарных локальных экспонентов Yu,v, 0 ^ u, v < n.

Exact formula for exponent of mixing digraph of feedback shift register.pdf Введение Изучение экспонентов примитивных матриц и графов началось в 1912 г. с работы Фробениуса [1]. Основные понятия и научные достижения отражены в обзоре [2] и ряде других работ. Получение точной аналитической формулы экспонента для того или иного класса матриц и орграфов - сложная комбинаторная задача, в связи с чем большинство работ в этой области посвящены верхним оценкам экспонентов, важным для приложений. Исследован класс преобразований g пространства n-мерных векторов, реализуемых регистром левого сдвига с нелинейной обратной связью f (ж0,... ,xn-i), имеющей m существенных переменных, в том числе ж0 (иначе реальная длина регистра меньше n), n ^ 3, 2 ^ m ^ n. Анализ перемешивающих свойств преобразований данного класса имеет прикладное значение для ряда систем защиты информации. Пусть множество вершин перемешивающего орграфа r(g), соответствующих номерам входных переменных преобразования g, есть {0,... ,n - 1}. Получены точные формулы экспонентов и локальных экспонентов двух частных классов перемешивающих орграфов регистровых преобразований. Первый класс орграфов имеет петлю в вершине n - 1, второй класс содержит контур (n - 1, n - 2) длины 2. 1. Структурные свойства перемешивающих орграфов регистровых преобразований Рассмотрим преобразование g двоичного регистра левого сдвига длины n с нелинейной функцией обратной связи f (ж0,... , xn-i). Обозначим D(g) = {di,... , dm} множество номеров всех существенных переменных функции f, где 0 = di < ... < dm ^ n -1. Тогда преобразованию g соответствует n-вершинный перемешивающий орграф r(g), имеющий n+m-1 дуг, где n дуг составляют гамильтонов контур (n-1,... , 0) и остальные дуги суть (d2, n- 1),... , (dm, n- 1). Таким образом, связный орграф T(g) есть объединение простых контуров Ci,... , Cm, где Ct = (n - 1, n - 2,..., dt), t = 1,... , m - 1, Cm = (n - 1, n - 2,..., dm) при dm < n - 1 и Cm есть петля в вершине n - 1 при dm = n - 1. Вершины dm,... , n - 1 являются общими для всех простых контуров. Обозначим: n-D(g) = {n-d' ■ i = 1,...,m}; ЛЖ (u,v) -множество длин всех путей из вершины u в вершину v; ЛЖ(u, v) = М0\\ЛЖ(u, v), где N0 - множество целых неотрицательных чисел. Определим элементарные локальные экспоненты орграфа r(g). По определению локальный экспонент (обозначается Yu,v) есть наименьшее натуральное число y, такое, что из u в v есть путь длины t при любом t ^ y [3]. В соответствии с определением Yu,v = 1 + maxЛW(u,v), 0 ^ u,v

Ключевые слова

локально примитивный орграф, перемешивающий орграф, примитивный орграф, регистр сдвига, экспонент орграфа, local primitivity of digraph, mixing digraph, primitive digraph, shift register, digraph exponent

Авторы

ФИООрганизацияДополнительноE-mail
Фомичев Владимир МихайловичФинансовый университет при Правительстве Российской Федерации; НИЯУ МИФИ; ФИЦ ИУ РАНдоктор физико-математических наук, профессор, профессор; профессор; ведущий научный сотрудникfomichev.2016@yandex.ru
Авезова Яна ЭдуардовнаАО «Позитив Текнолоджиз»аналитикavezovayana@gmail.com
Всего: 2

Ссылки

Frobenius G. Uber Matrizen aus nicht negativen Elementen // Sitzungsber K. Preuss. Akad. Wiss. 1912. P. 456-477.
Fomichev V. M., Avezova Ya. E., Koreneva A. M., and Kyazhin S. N. Primitivity and local primitivity of digraphs and nonnegative matrices //J. Appl. Industr. Math. 2018. V. 12. No. 3. P. 453-469.
Fomichev V. M. and Kyazhin S. N. Local primitivity of matrices and graphs //J. Appl. Industr. Math. 2017. V. 11. No. 1. P. 26-39.
 Точная формула экспонента перемешивающего орграфа регистрового преобразования | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/8

Точная формула экспонента перемешивающего орграфа регистрового преобразования | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/8