About the minimal primitive matrices.pdf Введение Для оценки свойства перемешивания входов композиции преобразований часто применяется матрично-графовый подход [1, гл. 10], основанный на определении экспонентов перемешивающих матриц (графов). Обзор основных результатов по этому направлению имеется в [2]. Аппаратная и программная реализация совершенных преобразований, реализующих полное перемешивание, затруднена необходимостью реализации большого количества связей между компонентами входных и выходных векторов. В связи с этим в работе введено и исследовано понятие минимальной примитивной матрицы, позволяющей оценить предельные возможности уменьшения количества связей между входом и выходом при сохранении свойства полного перемешивания у композиции преобразований. 1. Свойства минимальных примитивных матриц Обозначим через M0(n) множество квадратных 0,1-матриц порядка n, S(n) -множество подстановочных матриц, P(и) -множество примитивных матриц. Примитивная матрица (граф) называется минимальной, если после замены любой единицы нулём (после удаления любой дуги) получается непримитивная матрица (граф). Обозначим множество минимальных примитивных матриц через Pmin(n). Утверждение 1. Если примитивные матрицы A,B G M0(n) сопряжены в S(и) и примитивны, то они одновременно минимальные или неминимальные. Рассмотрим на множестве M0(n) отношение частичного порядка: A ^ B ^ ai,j ^ bi,j для всех i,j = 1,... ,n, где A = (ai,j),B = (bi,j). Множество M0(n) образует решётку в смысле отношения где матрица, все элементы которой равны 1, является наибольшим элементом, а нулевая матрица - наименьшим. Подмножество примитивных матриц P(n) множества M0(n) является верхней полурешёткой. Минимальные примитивные матрицы - это все минимальные элементы верхней полурешётки P(n). 7 В частично упорядоченном множестве X антицепь Y назовем наибольшей, если она имеет наибольшую мощность, и максимальной, если любой элемент множества X сравним с некоторым элементом антицепи Y. Утверждение 2. Pmin(n) есть максимальная антицепь полурешётки P(n). Число единиц матрицы A Е M0(n) называется весом матрицы A (обозначается ||A||). Назовём k-м слоем подрешётки R решётки M0(n) подмножество (обозначается состоящее из матриц веса k, где k = 0,1,... , n . Заметим, что R(k) есть антицепь решётки R при всех k. Утверждение 3. При n > 3 выполнена оценка 3n! ^ |Pmin(n)| ^ Clm/2J, где m = n2. Нижняя оценка получена с использованием свойства P(ra+1)(n) С Pmin(n), где P(ra+1)(n) содержит три класса орграфов, порядки которых равны n!: 1) полный цикл с добавленной дугой (i - 1, i + 1), i Е {1,... , n} (рис. 1,a); 2) полный цикл с добавленной петлей в вершине i Е {1,..., n} (рис. 1,б); 3) класс графов, вид которых зависит от чётности числа n: при чётном n граф состоит из двух циклов длины 2 и l = n - 1 (рис. 1,в); при нечётном - из двух циклов длины 2 и l = n (рис. 1,г). В обоих случаях (2,1) = 1, поэтому в соответствии с критерием [3, с. 226] графы примитивные. a б вг Рис. 1. Примеры минимальных графов из P (ra+1)(n) Улучшение нижней оценки возможно на основе обобщения случая 3 (рассмотрения некоторых классов графов из слоев P (n+r)(n) при r > 1). 2. Высота примитивной матрицы Расстоянием по Хэммингу между 0,1-матрицами A и B (обозначается d(A,B)) называется число различных соответствующих элементов матриц A и B: d(A,B) = EKj ® bitj). Высотой примитивной матрицы A (обозначается h(A)) называется расстояние по Хэммингу между A и ближайшей минимальной примитивной матрицей M Е Pmin(n): h(a) = min d(A, M). M ePmin(ra) Величина h(A) является определённой мерой избыточности при построении связей между элементами входа и выхода преобразований информации. Алгоритм оценивания h(A) (метод координатного спуска): 1) последовательно просматривая элементы матрицы A, находим единицы; 2) заменяем найденный единичный элемент в матрице A нулевым и для полученной матрицы A' выполняем: - проверяем в A' наличие нулевых строк и столбцов; если таковые есть, возвращаемся к выполнению п. 2 для следующей единицы матрицы A; - матрицу A' без нулевых строк и столбцов проверяем на примитивность; - если матрица A' не примитивная, возвращаемся к матрице A, восстанавливаем замененную единицу и выполняем п. 2 для следующей единицы матрицы A; - примитивную матрицу A' проверяем на минимальность; - если A' минимальная, то определяем m - число единиц, заменённых нулями; - если A' не минимальная, то переходим к выполнению п. 1 для матрицы A'. На выходе алгоритма получим минимальную примитивную матрицу M, где h(A) ^ d(A,M) = m. Сложность алгоритма полиномиальная. Пусть ||A|| = k, где n < k ^ n2 для примитивной матрицы A. Тогда вычислительная сложность алгоритма в битовых операциях в худшем случае не превышает величины 0(k2n3 log n). Объём памяти требуется порядка O(n2) битов. Данный метод можно использовать для поиска минимальных матриц, близких к перемешивающим матрицам раундовых подстановок блочных шифров (DES, ГОСТ 28147-89 и др.).

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