Компьютерно-аналитическое исследование задач рюкзачного типа как средство анализа и совершенствования систем защиты информации

• Автор: Мурин, Дмитрий Михайлович
• Шифр специальности: 05.13.19
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Ярославль
• Количество страниц: 116 с. : ил.

Оглавление
Введение
Используемые обозначения
1. О порядке роста числа сверхрастущих и инъективных векторов и некоторых особенностях сильного модульного умножения
1.1. Задача о рюкзаке
1.2. Подсчет инъективных и сверхрастущих векторов
1.2.1. Математические основы проведенных компьютерных экспериментов по подсчету инъективных и сверхрастущих векторов с заданными размерностью и максимальным элементом
1.2.2. Алгоритм подсчета возрастающих инъективных векторов
1.2.3. Результаты компьютерных экспериментов
1.3. Оценки для функций ід (г, М) и К2(г. М)
1.3.1. Оценка сверху для функции Р) (г. М)
1.3.2. Оценка, снизу для функции ід (г. М)
1.3.3. Результаты компьютерных экспериментов
1.4. Алгоритм перечисления всех сверхрастущих векторов заданной размерности с фиксированным максимальным элементом
1.5. Некоторые особенности сильного модульного умножения
1.6. О монотонности функции ід (г. М)
1.7. Выводы
2. Модификация метода Лагариаса-Одлыжко решения Задачи о рюкзаке для случая Обобщенной Задачи о рюкзаке и случаев систем задач о рюкзаках
2.1. ЫА-приведенные базисы решетки
2.2. Алгоритм построения ЫА-приведенного базиса решетки
2.3. Об оценке числа точек целочисленной решетки, попадающих
в сферу малого радиуса в г-мерном пространстве
2.4. Метод Лагариаса-Одлыжко решения Задачи о рюкзаке
2.5. Метод решения Обобщенной Задачи о рюкзаке, основанный
на методе Лагариаса-Одлыжко
2.6. Метод решения систем обобщенных задач о рюкзаках
2.7. Метод решения систем задач о рюкзаках
2.8. Выводы

3. О некоторых свойствах образов трансформированных Задач. ЫХ-решатель
3.1. О верхней границе плотности инъективных векторов
3.1.1. О последовательности Штерна и результатах компьютерных экспериментов
3.1.2. О плотности инъективных векторов
3.2. Некоторые свойства образов трансформированных Задач
3.2.1. Задача о точном покрытии ос Задача о рюкзаке
3.2.2. Задача о раскрашиваемое ос Задача о рюкзаке
3.2.3. Задача 3-ВЫП ос Задача о рюкзаке
3.2.4. О коротком сведении Задачи 3-ВЫП к Задаче о рюкзаке
3.3. ЫХ-решатель
3.3.1. Конструкция ЫХ-решателя
3.3.2. Результаты компьютерных экспериментов
3.4. Выводы
Заключение
Список использованной литературы
Приложение

Введение
Ряд современных систем защиты информации и обеспечения информационной безопасности базируется на МР-полных Задачах Задачи из класса КР-полиых являются, в определенном смысле, «очень сложными» для решения [8,11,16.18]. поэтому, с одной стороны, представляет особый интерес изучение средств и систем защиты информации, для преодоления которых необходимо решить лежащую в их основе КР-но. шую Задачу, а с другой стороны. методы решения индивидуальных представителей МР-нолиых Задач представляются естественными методами анализа эффективности разрабатываемых средств и систем защиты информации. Одной из систем защиты информации, в основе которой лежит МР-полная Задача, является асимметричная система шифрования Меркля-Хеллмана [40]. основанная на КР-полной Задаче распознавания - Задаче о рюкзаке. В работах [24.25.43,47] по анализу этой системы были предложены методы решения некоторых множеств задач о рюкзаках - индивидуальных представителей вычислительной Задачи о рюкзаке. В диссертационной работе метод решения вычислительной Задачи о рюкзаке, предложенный Дж. Лагариасом п А. Одлыжко [43], модифицируется в метод решения вычислительной Обобщенной Задачи о рюкзаке п методы решения систем задач о рюкзаках. Кроме того, в диссертационной работе предлагается основанный на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке [43] метод решения за «приемлемое время» представителей МР-полных Задач - ЬЬЬ-решатель.
Зарождение теории КР-нолноты связывают с опубликованной в 1971 году работой С. Кука [29]. В этой работе была установлена важность понятия «полиномиальная сводимость Задач», выделен класс Задач распознавания свойств, которые могут быть решены за полиномиальное время на недетерминированном вычислительном устройстве (недетерминированной машине Тьюринга) (класс МР). Кроме того, было показано, что Задача о выполнимости конъюнктивной нормальной формы - представитель класса КР - обладает тем свойством, что любая другая Задача из класса МР может быть сведена к ней за полиномиальное время (то есть в определенном смысле Задача о выполнимости является самой сложной Задачей в классе МР). и установлено, что таким свойством могут обладать и другие задачи из класса КР (например. Задача о существовании в графе С клики с определенным числом вершин).

к к к и Выводимый вектор к І2 к к Выводимый вектор
X X X X (1.2,4,8) 0 0 2 2 (1,2,6.12)
0 0 0 1 (1,2,4, 9) 0 0 2 3 (1,2,6,13)
0 0 0 2 (1.2,4,10) 0 0 2 4 (1.2,6,14)
0 0 0 3 (1,2,4,11) 0 0 3 X (1.2,7,11)
0 0 0 4 (1,2,4,12) 0 0 3 1 (1.2,7,12)
0 0 0 5 (1,2,4.13) 0 0 3 2 (1,2,7,13)
0 0 0 6 (1,2,4.14) 0 0 4 X (1,2,8,12)
0 0 0 7 (1.2,4,15) 0 1 X X (1,3,5,10)
0 0 0 8 (1,2,4.16) 0 1 0 1 (1,3,5,11)
0 0 1 X (1,2,5,9) 0 1 0 2 (1,3,5,12)
0 0 1 1 (1,2,5,10) 0 1 0 3 (1,3,5,13)
0 0 1 2 (1,2,5,11) 0 1 0 4 (1,3,5,14)
0 0 1 3 (1,2,5,12) 0 1 1 X (1,3,6,11)
0 0 1 4 (1,2,5,13) 0 1 1 1 (1,3,6,12)
0 0 1 5 (1,2,5,14) 0 1 2 (1,3,6,13)
0 0 1 6 (1.2,5,15) 0 1 2 X (1,3,7,12)
0 0 2 X (1,2,6,10) 0 2 X X (1.4,6,12)
0 0 2 1 (1,2,6,11) 1 X X X (2,3,6,12)
Таблица 2. Пошаговое исполнение алгоритма
найти по следующей формуле:
Е ЕЕ- Е
^=2Г ^ к—0 к'2—О А‘т_1—О

Ыт) - 1):
т=.;+2'-1+А-12'-2^Ь22'-3+...+А-,_221+;сг-12и
где ф(т) - функция Эйлера. В этой формуле первая сумма отвечает за выбор максимального элемента сверхрастущего вектора, последовательность сумм по индексам Ад,.... Лтг— ] - за общее число сверхрастущих векторов размерности г с фиксированным максимальным элементом последняя сумма - за выбор модуля из интервала (Хл=г а-,, М], а <р(гп) — 1 - за выбор множителя с учетом того, что он не равен 1.