Оценки скорости сходимости в предельных теоремах для совместных распределений части характеристик случайных двоичных отображений // ПДМ. <...> МАТЕМАТИЧЕСКИЕ МЕТОДЫ КРИПТОГРАФИИ 31–52 Марков В. Т., Михалёв А. В., Грибов А. В., Золотых П. А., Скаженик С. С. <...> Квазигруппы и кольца в кодировании и построении криптосхем // ПДМ. <...> О вероятности протяжки однобитовой разности через сложение и вычитание по модулю // ПДМ. <...> ДИСКРЕТНЫЕ МОДЕЛИ РЕАЛЬНЫХ ПРОЦЕССОВ 61–72 Емеличев В. А., Коротков В. В. <...> Исследование устойчивости решений векторной инвестиционной булевой задачи в случае метрики Гельдера в критериальном пространстве // ПДМ. <...> Развитие метода непрерывных асинхронных клеточных автоматов для моделирования турбулентных потоко // ПДМ. <...> Одним из положительных криптографических свойств преобразований вектор{S(g1), . . . ,S(gn)}, где S(gj)—множество номеров существенных переменных координатной функции gj(x1, . . . ,xn), j = 1, . . . ,n. <...> Однако подобный вывод неприменим к функциям, используемым в криптографических системах, так как они выбираются не случайно, а из отображений с рядом заданных свойств. <...> Поэтому изучение перемешивающих свойств криптографических функций—актуальная задача криптографического анализа. <...> В частности, показатель степени раундовой подстановки блочного шифра, при которой достигается хорошее перемешивание, является определяющим при выборе разработчиком числа циклов шифрования. <...> Обозначим Γ(g) перемешивающий n-вершинный орграф преобразования g, в котором пара (i, j) является дугой тогда и только тогда, когда i ∈ S(gj), i, j ∈ {1, . . . ,n}. <...> Матрицу M(g) смежности вершин графа Γ(g) называют перемешивающей матрицей преобразования g. <...> При эпиморфизме ϕ матрицеM соответствует орграф Γ с множеством вершин {1, . . . ,n} и множеством дуг U, где (i, j) ∈ U ⇔ mi,j > 0. <...> Эпиморфизм ϕ всякой неотрицательной матрице A ставит в соответствие орграф Γ = ϕ(A), матрица смежности вершин которого есть v(A). <...> Следовательно, орграф Γ = ϕ(A) полный в том и только в том случае, если A > 0 <...>
Прикладная_дискретная_математика_№4_2012.pdf
ПДМ. 2012. № 4(18).
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРИКЛАДНОЙ
ДИСКРЕТНОЙ МАТЕМАТИКИ
5–13
Когос К. Г., Фомичев В. М. Положительные свойства неотрицательных матриц // ПДМ. 2012. №
4(18). C. 5–13.
14–30
Панков К. Н. Оценки скорости сходимости в предельных теоремах для совместных распределений
части характеристик случайных двоичных отображений // ПДМ. 2012. № 4(18). C. 14–30.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ КРИПТОГРАФИИ
31–52
Марков В. Т., Михалёв А. В., Грибов А. В., Золотых П. А., Скаженик С. С. Квазигруппы и кольца в
кодировании и построении криптосхем // ПДМ. 2012. № 4(18). C. 31–52.
53–60
Пестунов А. И. О вероятности протяжки однобитовой разности через сложение и вычитание по
модулю // ПДМ. 2012. № 4(18). C. 53–60.
ДИСКРЕТНЫЕ МОДЕЛИ РЕАЛЬНЫХ ПРОЦЕССОВ
61–72
Емеличев В. А., Коротков В. В. Исследование устойчивости решений векторной инвестиционной
булевой задачи в случае метрики Гельдера в критериальном пространстве // ПДМ. 2012. № 4(18).
C. 61–72.
73–81
Тимчук Г. Д., Жихаревич В. В. Развитие метода непрерывных асинхронных клеточных автоматов
для моделирования турбулентных потоко // ПДМ. 2012. № 4(18). C. 73–81.
ИСТОРИЧЕСКИЕ ОЧЕРКИ ПО ДИСКРЕТНОЙ
МАТЕМАТИКЕ И ЕЁ ПРИЛОЖЕНИЯМ
82–107
Токарева Н. Н. Об истории криптографии в России // ПДМ. 2012. № 4(18). C. 82–107.
АНАЛИТИЧЕСКИЕ ОБЗОРЫ
Стр.1
108–122
Агибалов Г. П., Панкратова И. А. Sibecrypt'12. Обзор докладов // ПДМ. 2012. № 4(18). C. 108–122.
Стр.2
ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА
2012
Теоретические основы прикладной дискретной математики
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ
УДК 519.6
ПОЛОЖИТЕЛЬНЫЕ СВОЙСТВА НЕОТРИЦАТЕЛЬНЫХ МАТРИЦ
К.Г. Когос∗, В.М. Фомичев∗∗
∗Национальный исследовательский ядерный университет (МИФИ), г. Москва, Россия
∗∗Финансовый университет при Правительстве Российской Федерации, г. Москва, Россия
E-mail: fomichev@nm.ru
Дан обзор результатов исследования примитивности графов (неотрицательных
матриц) и некоторых направлений обобщения. Приведены оценки экспонентов
различных классов графов и систем графов (матриц и систем матриц).
Ключевые слова: примитивный граф, примитивная матрица, экспонент, субэкспонент.
Одним
из положительных криптографических свойств преобразований вектор{S(g1),
. . . ,S(gn)}, где S(gj)—множество номеров существенных переменных координатной
функции gj(x1, . . . ,xn), j = 1, . . . ,n. Наилучшее перемешивание достигается,
если каждая из координатных функций преобразования g зависит от всех переменных,
то есть S(gj) = {1, . . . ,n}, j = 1, . . . ,n. Такие преобразования принято называть совершенными.
Обобщениями свойства совершенности функций являются такие свойства,
как строгий лавинный критерий, критерии распространения, свойство «бент».
Почти все преобразования векторного пространства Pn над конечным полем P являются
совершенными при n→∞. Однако подобный вывод неприменим к функциям,
используемым в криптографических системах, так как они выбираются не случайно,
а из отображений с рядом заданных свойств. Поэтому изучение перемешивающих
свойств криптографических функций—актуальная задача криптографического анализа.
Некоторые
функции с полным перемешиванием обладают свойством распространения
искажений входных данных, что позволяет использовать их в криптосистемах
аутентификации. С другой стороны, к функциям шифрования с неполным перемешиванием
входов применимы методы определения ключа типа последовательного опробования,
что делает привлекательным использование в криптосистеме шифрования
совершенных преобразований.
Аппаратная или программная реализация совершенных преобразований затруднена
в связи с необходимостью реализации функций от большого числа переменных.
Поэтому для хорошего перемешивания используются итерации (возведение в степень)
преобразования с относительно слабыми перемешивающими свойствами. Показатель
степени преобразования, при которой достигается хорошее перемешивание, является
ных пространств является хорошее перемешивание, то есть зависимость каждой
координатной функции от всех переменных. Перемешивающие свойства преобразования
g пространства Pn над полем P, заданного системой координатных
функций {g1(x1, . . . ,xn), . . . , gn(x1, . . . ,xn)}, определяются системой множеств
№4(18)
Стр.3