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

Скачать электронную версию публикации