On local primitiveness of graphs and nonnega-tive matrices.pdf Пусть M0(n) —множество всех квадратных неотрицательных матриц порядка n, A Е M0(n), J = {j^,... , jr}, 0 = J С {1,... ,n}; A(J2) —подматрица порядка r, полученная из A вычёркиванием строк и столбцов с номерами j = j1,... ,jr. Множество матриц, для которых подматрица A(J2) неотрицательна, обозначим M0(J2). Матрицу A назовем J2-положительной, если положительна подматрица A(J2). Обозначим M+(J2) полугруппу по умножению J2-положительных матриц. Матрица A называется квазиположительной, если все её строки и столбцы отличны от нулевых. Матрица A называется J2-квазиположительной, если квазиположительной является подматрица A( J2). Обозначим Q(J2) множество J2-квазиположительных матриц. Квазиположительную матрицу A назовём J2-примитивной, если положительна подматрица A*(J2) матрицы A* при любом натуральном t ^ y; наименьшее такое число y назовём J2-экспонентом матрицы A и обозначим J2-expA. Множество J2-прими-тивных матриц обозначим P(J2). Подматрицу размера n х r, полученную из A вычёркиванием столбцов с номерами j = j1,...,jr, обозначим A(J) и назовём её в соответствующих условиях J-положи-тельной (J-квазиположительной, J-примитивной). Множества таких матриц обозначим соответственно M+(J), Q(J) и P(J). Наименьшее натуральное число y, при котором подматрицы A*( J) строго положительны при любом t ^ y , назовём J-экспонентом матрицы A и обозначим J-expA. Обозначим S(J2) группу подстановочных матриц порядка n, для которых любой элемент i Е J неподвижный. Утверждение 1. При любом непустом подмножестве J С {1,... , n}, n> 1, имеет место: 1) M+(J2) С P(J2) С Q(J2); 2) S(J2) С Q(J2), при этом S(J2) U P(J2) = 0; 3) множество Q(J2) образует моноид относительно умножения, M+(J2) —идеал моноида Q(J2). Пусть A,B Е M0(n), A = (aj), B = (bj), определим отношение A ^ B ^ ajj ^ bjj, i, j = 1,..., n. Утверждение 2. 1) Пусть J ^ I, тогда если матрица A не J2-примитивная, то она не I^примитивная; если матрица A является I2-примитивной, то она J2-примитивная и J2-expA ^ 12-expA; аналогичные соотношения верны для J-примитивности и I-примитивности. 2) Если матрица A не J2-примитивная, то и матрица A(J2) не примитивная; если матрица A(J2) примитивная, то матрица A является J2-примитивной и J2-expA ^ expA(J2). 3) Если A ^ B и A является J2-примитивной, то и B является J2-примитивной и J2-expA ^ J2-expB. Утверждение 3. Если матрицы A,B Е M0(J2) сопряжены в группе S(J2), то A и B одновременно или J2-примитивны, или не J2-примитивны. Обозначим через T(A) орграф, матрицей смежности вершин которого является носитель матрицы A. Известно, что матрица A и граф T(A) одновременно примитивны или не примитивны. Теорема 1. Граф T(A) является J2-примитивным тогда и только тогда, когда r(A) имеет сильносвязный примитивный подграф с множеством вершин, содержащим J. Теорема 2. Связный граф T(A) является J-примитивным тогда и только тогда, когда r(A) имеет сильносвязный примитивный подграф U с множеством вершин, содержащим J, и из каждой вершины i Е U достижимо множество вершин U. Следствие 1. Пусть J2-expA = y, J-expA = 8. Если граф r(A) является J-примитивным, то y ^ 8 ^ Y + max p(i, U), где p(i, U) —длина кратчайшего пути из вершиi ны i Е U в ближайшую вершину j Е U. Ряд генераторов гаммы построен на основе последовательного соединения управляющего и генерирующего автоматов [1, гл. 18], при этом выходная гамма образуется с помощью функции от некоторого подмножества J знаков состояний генерирующего автомата. Положительным криптографическим свойством такого генератора является существенная зависимость всех знаков множества J от всех знаков начального состояния генератора. В связи с этим рассмотрим автономный автомат без выхода A, построенный как последовательное соединение двух регистров правого сдвига длины n и m соответственно с функциями обратной связи f (x) и g(x). Пусть Vr —множество двоичных r-мерных векторов, r = 1, 2,...; A — автомат с множеством состояний Vn+m, выходным алфавитом управляющего регистра V1 и функцией переходов h: h(x1, . . . , xni xn+1, . . . , xn+m) (f (x1, ... , xn) , x1, . . . , xn-1, xn ф g(xn+1, ... , xn+m) , xn+1, ... , xn+m-1). Перемешивающая матрица M (порядка m + n) преобразования h генератора имеет вид м=(A B где A — перемешивающая матрица порядка n преобразования управляющего регистра; C — матрица порядка m, совпадающая при фиксированном xn с перемешивающей матрицей преобразования генерирующего регистра; в матрице B = (bij) порядка n х m элемент bn,n+1 = 1, а остальные элементы равны 0. Теорема 3. Пусть J = {n + 1,... ,n + m}, функция g(x) существенно зависит от переменных с номерами j1,... ,jr,m, где 1 ^ j1 < ... < jr < m, 1 ^ r < m, НОД (j1,... ,jr ,m) = d ^ 1. Тогда матрица M преобразования генератора J-примитив-на, если и только если d = 1; в случае J-примитивности верны следующие оценки: 1) J-exp M ^ max{n + j1(m — 1), exp C}; 2) J-exp M ^ n + exp C. Величины exp C и J-exp M можно оценить через характеристики генератора. 1) Из [2, c. 227] следует, что exp C ^ m + j1(m — 2), тогда в соответствии с теоремой 3, п. 1 J-exp M ^ max{m, n + j{} + j1(m — 2). 2) Пусть среди чисел j1,... ,jr ,m имеется пара взаимно простых чисел, например (j1,j2) = 1, тогда из [3, теорема 1,б] следует, что exp C ^ 2m + j2j1 — j2 — 2j1. В этом случае в соответствии с теоремой 3, п. 1 J-exp M ^ max{n + j1(m — 1), 2m + j2j1 — j2 — 2j1}. т? о - ^ m(j1 — 2)+ j1 n s ■ ( л\ Если, в частности, j1 > 2 и j2 ^ -, то exp C ^ j1(m — 1), то есть оценка j1 — 1 теоремы 3, п. 2 точнее. Тогда в соответствии с теоремой 3, п. 2 J-exp M ^ n + 2m + j2j1 — j2 — 2j1.

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