Положительные свойства неотрицательных матриц | ПДМ. 2012. № 4(18).

Положительные свойства неотрицательных матриц

Дан обзор результатов исследования примитивности графов (неотрицательных матриц) и некоторых направлений обобщения. Приведены оценки экспонентов различных классов графов и систем графов (матриц и систем матриц).

Positive properties of non-negative matrices.pdf Одним из положительных криптографических свойств преобразований векторных пространств является хорошее перемешивание, то есть зависимость каждой координатной функции от всех переменных. Перемешивающие свойства преобразования g пространства Pn над полем P, заданного системой координатных функций {g1(x1,... , xn),... , gn(x1,... , xn)}, определяются системой множеств {S(g1),... , S(gn)}, где S(gj) —множество номеров существенных переменных координатной функции gj(xi,... , xn), j = 1,... ,n. Наилучшее перемешивание достигается, если каждая из координатных функций преобразования g зависит от всех переменных, то есть S(gj) = {1,... , n}, j = 1,... , n. Такие преобразования принято называть совершенными. Обобщениями свойства совершенности функций являются такие свойства, как строгий лавинный критерий, критерии распространения, свойство «бент». Почти все преобразования векторного пространства Pn над конечным полем P являются совершенными при n ^ то. Однако подобный вывод неприменим к функциям, используемым в криптографических системах, так как они выбираются не случайно, а из отображений с рядом заданных свойств. Поэтому изучение перемешивающих свойств криптографических функций — актуальная задача криптографического анализа. Некоторые функции с полным перемешиванием обладают свойством распространения искажений входных данных, что позволяет использовать их в криптосистемах аутентификации. С другой стороны, к функциям шифрования с неполным перемешиванием входов применимы методы определения ключа типа последовательного опробования, что делает привлекательным использование в криптосистеме шифрования совершенных преобразований. Аппаратная или программная реализация совершенных преобразований затруднена в связи с необходимостью реализации функций от большого числа переменных. Поэтому для хорошего перемешивания используются итерации (возведение в степень) преобразования с относительно слабыми перемешивающими свойствами. Показатель степени преобразования, при которой достигается хорошее перемешивание, является важной криптографической характеристикой. В частности, показатель степени раун-довой подстановки блочного шифра, при которой достигается хорошее перемешивание, является определяющим при выборе разработчиком числа циклов шифрования. Матрицу A над полем действительных чисел называют положительной (неотрицательной), если положительны (неотрицательны) все её элементы, при этом пишут A > 0 (A ^ 0). Носителем неотрицательной матрицы A = (ai,j) называется 0,1-мат-рица v(A) = (v(ai,j)), где v(ai,j) = 1, если a^j > 0, и v(ai,j) = 0, если a^j = 0, при всех допустимых i, j. Заметим, что v есть гомоморфизм мультипликативного моноида неотрицательных матриц над полем действительных чисел на мультипликативный моноид 0,1-матриц, где v(AB) = v(A) • v(B). Точное определение множества {S(g\),...,S(gn)} является во многих случаях сложной вычислительной задачей. Поэтому при исследовании перемешивающих свойств степеней преобразований применяется оценочный теоретико-графовый или матричный подход. Обозначим Г(д) перемешивающий n-вершинный орграф преобразования д, в котором пара (i, j) является дугой тогда и только тогда, когда i Е S(gj), i, j Е {1,... , n}. Матрицу M(д) смежности вершин графа Г(д) называют перемешивающей матрицей преобразования д. Суть оценочного подхода состоит в исследовании степеней матрицы M(д) и определении наименьшего натурального числа t, такого, что (M(д)) > 0. Корректность такого подхода вытекает, например, из следствия 2 теоремы 10.3 [1]: если матрица (M(д)) не положительна, то преобразование д1 не совершенно. Оценочный теоретико-графовый или матричный подход реализуется существенно проще с точки зрения сложности вычислений, чем точное вычисление множеств существенных переменных. При исследовании перемешивающих свойств часто используется эпиморфизм ^ мультипликативного моноида неотрицательных матриц порядка n на моноид n-вер-шинных орграфов, где умножение графов определено как умножение бинарных отношений. При эпиморфизме ^ матрице M соответствует орграф Г с множеством вершин {1,... , n} и множеством дуг U, где (i, j) Е U ^ mi,j > 0. При эпиморфизме ^ выполнено: M > 0, если и только если граф Г = 0 положительных элементов на главной диагонали для любого h ^ k при целом неотрицательном k. Тогда exp A ^ 2n - d + k - 1. Отсюда следует, что если матрица A имеет не менее d > 0 положительных элементов на главной диагонали, то exp A ^ 2n - d - 1, и если положительны все элементы на главной диагонали, то exp A ^ n - 1. Пусть матрица A примитивна и матрица A + ... + Ah, h ^ 1, имеет не менее d > 0 положительных элементов на главной диагонали. Тогда [3, с. 409] exp A ^ n - d + h(n - 1). Экспонент примитивной симметричной матрицы [3, с. 409] удовлетворяет оценке exp A ^ 2(n - 1). Замечание 1 [4, с. 140]. В связи с абсолютной оценкой (1) отметим, что Далмей-джем (Dulmage A. L.) и Мендельсоном (Mendelsohn N. S.) выделены «лакуны», то есть некоторые числа, не превышающие n2 - 2n + 2 и не являющиеся показателями примитивности какой-либо матрицы порядка n. Таковы, например, числа из интервалов (n2 - 3n + 4, (n - 1)2) и (n2 - 4n + 6, n2 - 3n + 2). При чётном n «лакуной» является интервал (n2 - 4n + 6, (n - 1)2), объединяющий оба предыдущих. В [5] данные результаты усилены. Показано, что для любых целых n, t не существует примитивной матрицы порядка n, экспонент которой удовлетворяет неравенствам n2 - tn + 1(t + 1)2 < exp A < n2 - (t - 1)n + t - 2. Замечание 2 [2, с. 243]. При n ^ то случайная равновероятная 0,1-матрица порядка n с вероятностью, стремящейся к единице, является примитивной и имеет экспонент равный двум. Матрица A порядка n называется частично разложимой, если у нее есть нулевая подматрица размера r х s,r + s = n. Матрица A вполне неразложима, если она не является частично разложимой. Известно [3, с. 300], что вполне неразложимая матрица A примитивна и exp A ^ n - 1. Критерий примитивности матрицы A дан ниже в связи с рассмотрением орграфа Г = p(A). 2. Примитивность графов Примитивность графа определяется естественным образом: граф Г примитивен, если примитивна матрица смежности его вершин, то есть неотрицательная матрица A и орграф Г = 2 рассмотрим n-вершинный орграф Г, состоящий из гамильтонова контура C = (1, 2,... , n), к которому добавлена дуга (i, j), где вершины i, j расположены на контуре C на расстоянии 2, i, j Е {1,... , n}. Множество n-вершинных орграфов, изоморфных орграфу Г, назовём n-вершинными графами Виландта и обозначим это множество Tw (n). При любом n > 2 множество Tw(n) состоит из n! изоморфных графов; абсолютная оценка Виландта достигается на графах Виландта, и только на них. Для остальных примитивных n-вершинных орграфов Г при нечётном n > 3 верна достижимая оценка (в соответствии с известными «лакунами») exp Г ^ n2 — 3n + 4. Верхняя граница экспонента примитивного орграфа может быть понижена [3, с. 227], если в орграфе известна длина простого контура. Пусть Г — примитивный орграф с n вершинами, l —длина кратчайшего простого контура в Г, тогда exp Г ^ n + l(n — 2). (2) В частности, если в примитивном орграфе имеется петля, то exp Г ^ 2n — 2. Граница (2) экспонента примитивного орграфа может быть понижена [7], если в орграфе известны длины l и Л двух простых контуров, где (l, Л) = 1. Пусть в n-вершин-ном орграфе Г имеются простые контуры C и C длины соответственно l и Л, где n > 2, 1 < Л < l ^ n и (l, Л) = 1. Обозначим C П C' пересечение множеств вершин контуров C и C'. Тогда 1) если C П C = 0, то exp Г ^ 1л — 2l — 3Л + 3n; 2) если C П C = H, где |H| = h > 0, то exp Г ^ 1л — l — 3Л + h + 2n. Отсюда следует, что для любого примитивного n-вершинного орграфа Г при n > 2 верно: 1) если контуры C и C не имеют общих вершин, то n2 n 1 Т + 2 + 4; n + 1 "n + Г _ 2 _ 2 exp Г ^ 2) если контуры C и C имеют h общих вершин, где 1 ^ h ^ Л, то exp Г ^ n + h + 2 "n + h + 2" _ 2 _ 2 - 2h - n ^ n2 - 2n + 2. В [8] получена оценка диаметра и экспонента nr-вершинного перемешивающего графа Г(^) обратимого преобразования ^ регистра сдвига длины n над множеством V двоичных r-мерных векторов, где n, r — натуральные (такие графы возникают при рассмотрении обобщения блочных шифров Фейстеля). Подстановка ^ такого регистра сдвига имеет вид ^(yi,...,yn) = (У2,...,Уп,^(У2 ,...,Уп) ф y^ где y1,..., yn G Vr; ^(y2,..., yn) называется функцией усложнения. Пусть подстановка ^ задается системой булевых координатных функций {^1(x1, x2, ... ,xnr), ^2(x1,x2,... ,xnr),..., ^nr(x1,x2,... ,xnr)}. Тогда функции усложнения ^(y2, ... ,yn) соответствует r-вершинный граф Г^: пара (v,w) образует дугу тогда и только тогда, когда функция ^(n-1)r+w зависит существенно от некоторой переменной из множества {xv,xr+v,... ,X(n-1)r+v}. Показано, что перемешивающий граф Г(^) сильно связен тогда и только тогда, когда сильно связен граф Г^. Получено, что если граф Г^ сильносвязный и diam Г^ ^ d, то 1) diam Г(^) ^ (n - 1) ■ min{d, r - 1} + n; 2) если граф Г(^) примитивный и ^(y2,..., yn) = ^(yn,... , y2) (в этом случае алгоритм блочного шифрования инволютивен), то diam^^) ^ n/2 ■ min{d, r - 1} + n; 3) если граф Г(^) примитивный, то exp^^) ^ n2r + nr - 2n. В [3, с. 398] дана оценка экспонентов турнира, то есть ориентированного n-вершин-ного орграфа Tn без петель, в котором каждая пара i, j различных вершин соединена ровно одной дугой. Турнир Tn называется приводимым, если существует такое разбиение множества вершин на два подмножества, что в Tn присутствуют все дуги, направленные из первого блока разбиения во второй блок. В противном случае турнир называется неприводимым. Показано, что при n ^ 4 турнир Tn примитивен тогда и только тогда, когда он неприводим. Экспонент турнира Tn оценивается при n ^ 5 через его диаметр d: d ^ exp Tn ^ d + 3. В общем случае 3 ^ exp Tn ^ n - 1. При n ^ 6 и 3 2, справедливо неравенство 1 ( n — 1 \ , n — 1 - 29---5) , k > 6--1, 2 V k + 1 / n + 1 ' exp Г ^ < 1 /11n — 6 \ , n — 1 n + - -;--3) , k ^ 6--1. 2 V k + 1 / n + 1 Для любого Г Е P(n, k, 1), где k > 2, выполнено fn — 1 n — 2 \ expr«4 F+T+—)—2 Универсальный критерий примитивности орграфа Г [3, с. 226] определяется длинами его простых контуров. Если Ci,... , C есть все простые контуры орграфа Г длин li,... , lfc соответственно, то сильносвязный орграф Г примитивный, если и только если (li, — , lk) = 1. Периодом вершины i орграфа называется наибольший общий делитель таких чисел k, что > 0, i = 1,... , n. Иными словами, период d вершины i равен наибольшему общему делителю длин всех контуров, проходящих через вершину i в орграфе Г. Неотрицательная матрица A = (ai;j) порядка n > 1 называется неразложимой (или неприводимой), если для всех i, j = 1,..., n существует t Е N, такое, что a(tj > 0, где A = (j Это означает, что орграф Г = 1. Если d = 1 для некоторой вершины орграфа Г, то матрица называется апериодической (или ациклической). Универсальный критерий примитивности на матричном языке имеет вид [3, с. 392]: неотрицательная матрица A примитивна тогда и только тогда, когда A неразложима и апериодична. Сумма неразложимой матрицы A и единичной матрицы I является примитивной матрицей (ей соответствует граф с n петлями), и exp(A + I) ^ n — 1. Достаточные условия примитивности орграфа Г(^) подстановки ^ регистра сдвига длины n над множеством Vr двоичных r-мерных векторов получены в [8]. Сильносвязный граф Г(^) примитивен, если выполнено любое из следующих условий: 1) координатная функция ^m зависит существенно от переменной xm при некотором m G {(n - 1)r + 1, (n - 1)r + 2,..., nr}, в этом случае exp Г(^) ^ 2nr - 2; 2) ^(y2,..., yn) = ^(yn,... , y2) и при некоторых m G {(n-1)r+1, (n-1)r+2,... , nr} и ^ G {1,... , r} координатная функция зависит существенно от переменной xjr+M при n - 2j = 1, в этом случае expT(^) ^ (ln/2)2 + n(r - l) - 2, где l — длина кратчайшего цикла графа Г^, проходящего через дугу m). В [10] исследован алгоритм «поиска в глубину», используемый для определения длин всех простых циклов сильносвязного n-вершинного орграфа. Вычислительная сложность алгоритма оценивается величиной порядка O(n2 log n), где элементарной операцией считается обращение к памяти и распознавание смежности двух вершин. В [10] исследован также алгоритм распознавания примитивности n-вершинного орграфа и вычисления его экспонента, основанный на быстром возведении в степень матрицы смежности вершин. Алгоритм требует O(n3 log n) операций сложения и умножения в поле GF(2). 2.2. Свойства экспонентов неориентированных графов В [7] сформулированы равносильные критерии примитивности неориентированных графов (далее просто графов) при условии, что ребро можно считать циклом длины 2: 1) связный n-вершинный граф G примитивен тогда и только тогда, когда в G имеется простой цикл нечётной длины; 2) связный n-вершинный граф G примитивен тогда и только тогда, когда G не является двудольным. Универсальная оценка экспонента примитивного графа [3, с. 409] значительно ниже аналогичной оценки для примитивных орграфов. Если n-вершинный граф G примитивен, то exp G ^ 2(n - 1). (3) Рассмотрим n-вершинный граф G. Обозначим при i = j, где i,j G {1,...,n}: w(i, j) — путь из i в j; [i, j] — кратчайший путь из i в j; [i, i] — кратчайший цикл, проходящий через вершину i; len[i, j] —длина пути [i, j], измеряемая числом рёбер графа G, составляющих путь. Обозначим через e(C) эксцентриситет цикла C в неориентированном графе G, т. е. e(C) = max{min len[i, j ]}. i 1 можно уточнить [7]: если l — длина длиннейшего простого цикла C нечётной длины в примитивном n-вершинном графе G, 1 ^ l ^ n, то exp Г ^ 2e(C) + l - 1 ^ 2n - l - 1. Если простые циклы нечётных длин покрывают множество вершин графа G, то exp Г ^ n - 1. Построено множество графов [7], на которых достигается верхняя граница неравенства (3). Обозначим через Гр(n) множество примитивных n-вершинных графов, состоящих из гамильтонова пути и петли, инцидентной одной из концевых вершин. При любом n > 1 множество Гр(n) состоит из n! изоморфных графов; абсолютная оценка exp Г = 2n - 2 достигается на графах G из множества Гр (n), и только на них. 3. Оценки субэкспонентов и множественных экспонентов систем матриц Неотрицательную матрицу A называют субпримитивной, если AM > 0, где t Е N, A[1,t] = A + A2 + ... + A*. Субэкспонентом матрицы A называется наименьшее а Е N, такое, что A[1'°"] > 0, и обозначается sbxp A. Если матрица A не субпримитивна, то положим sbxp A = то. Понятия экспонента и субэкспонента могут быть обобщены на систему квадратных неотрицательных матриц П = {M1,...,Mp} одинакового размера. Пусть Np = = {1,... ,p}, Np —множество всех слов в алфавите Np. Слову w = s1... s из Np при заданной системе матриц П соответствует матрица MS1 ... MSl, являющаяся элементом мультипликативной полугруппы (П) неотрицательных матриц, порождённой системой П. Обозначим MS1 ... MSl = M(w) = (mi;j(w)). Экспонентом системы матриц П (обозначается exp П) называется наименьшая длина l слова w Е N^, при котором M(w) > 0. Если такого слова не существует, то полагаем exp П = то. Субэкспонентом системы матриц П (обозначается sbxp П) называется наименьшая длина l слова w Е Np, при котором M [1'1] (w) > 0, где MWl (w) = Ms1 + Ms1 Ms2 + ... + +M(w). Если такого слова не существует, то полагаем sbxp П = то. Известно [11], что для любой системы П квадратных неотрицательных матриц одинакового размера справедливо sbxp П ^ exp П. Пусть GS — орграф с множеством вершин {1,... ,n}, где все дуги помечены числом s, а MS = (mj(s)) —матрица смежности вершин орграфа GS, s = 1,... ,p. Тогда объединение графов G(p) = G1 U ... U Gp есть либо орграф, либо мультиграф (в зависимости от множества объединяемых дуг), которому соответствует система матриц смежности П = {M1,...,Mp}. При этом любой путь длины l в мультиграфе (графе) G(p) помечен словом в алфавите Np длины l. Отсюда система неотрицательных матриц П и соответствующий ей мультиграф G(p) одновременно примитивны (субпримитивны) или не примитивны (не субпримитивны), в случае примитивности (субпримитивности) их экспоненты (субэкспоненты) равны. Для любого мультиграфа G(p) справедливо [11] diam G(p) ^ sbxp П, причём если G = G1 = ... = Gp, то diam G = sbxp П. В [11] показано, что мультиграф G(p) сильно связен тогда и только тогда, когда он субпримитивен. Если n-вершинный мультиграф G(p) сильно связен, то при n ^ 4 , ^ (n2 — 2)(n — 1) sbxp П ^-^-. Система квадратных неотрицательных матриц одинакового размера называется множественно примитивной, если существует натуральное l, такое, что для любого слова длины l в алфавите N* имеет место неравенство M(w) > 0. Минимальное число k, обладающее таким свойством, называется множественным экспонентом системы матриц П. В [12] доказано, что множество вполне неразложимых матриц порядка n является множественно примитивным и для множественного экспонента k имеет место оценка k ^ n — 1. Известна достижимая оценка множественного экспонента любой множественно примитивной системы П квадратных неотрицательных матриц порядка n: k ^ 2n - 2. Неотрицательная матрица A порядка n называется r-неразложимой, 0 ^ r ^ n, если она не содержит нулевой подматрицы размера p х q, p + q = n - r + 1, 0

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

примитивный граф, примитивная матрица, экспонент, субэкспонент, primitive graphs, primitive matrices, exponent, subexponent

Авторы

ФИООрганизацияДополнительноE-mail
Когос Константин ГригорьевичНациональный исследовательский ядерный университет (МИФИ), г. Москвастудент факультета кибернетики и информационной безопасностиk.kogos@mail.ru
Фомичев Владимир МихайловичФинансовый университет при Правительстве Российской Федерации, г. Москвастарший научный сотрудник, доцент, доктор физико-математических наук, профессор кафедры математикиfomichev@nm.ru
Всего: 2

Ссылки

Фомичев В. М. Методы дискретной математики в криптологии. М.: Диалог-МИФИ, 2009.
Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. No. 52. S. 642-648.
Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000.
Носов В. А., Сачков В. Н., Тараканов В. Е. Комбинаторный анализ. Неотрицательные матрицы, алгоритмические проблемы // Итоги науки и техники. Сер. теория вер., матем. статист., теорет. киберн. 1983. Т. 21. С. 120-178.
Lewin M. and Vitek Y. A system of gaps in the exponent set of primitive matrices // Illinois J. Math. 1981. Issue 1. No. 25. P. 87-98.
Берж К. Теория графов и её применение. М.: ИЛ, 1962.
Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(12). С. 101-112.
Коренева А. М., Фомичев В. М. Об одном обобщении блочных шифров Фейстеля // Прикладная дискретная математика. 2012. №3(17). С. 34-40.
Князев А. В. Оценки экстремальных значений основных метрических характеристик псевдосимметрических графов: дис.. докт. физ.-мат. наук. М., 2002. 203с.
Кяжин С. Н., Фомичев В. М. О примитивных наборах натуральных чисел // Прикладная дискретная математика. 2012. №2(16). С. 5-14.
Фомичев В. М. Свойства путей в графах и мультиграфах // Прикладная дискретная математика. 2010. №1(7). С. 118-124.
Сачков В. Н. Вероятностные преобразователи и правильные мультиграфы // Труды по дискретной математике. 1997. Т. 1. С. 227-250.
Сачков В. Н., Ошкин И. Б. Экспоненты классов неотрицательных матриц // Дискретная математика. 1993. Т. 5. Вып. 2. С. 150-159.
 Положительные свойства неотрицательных матриц | ПДМ. 2012. № 4(18).

Положительные свойства неотрицательных матриц | ПДМ. 2012. № 4(18).

Полнотекстовая версия