Содержание к диссертации
Введение
1. О порядке роста числа сверхрастущих и инъективных векторов и некоторых особенностях сильного модульного умножения 13
1.1. Задача о рюкзаке 14
1.2. Подсчет инъективных и сверхрастущих векторов
1.2.1. Математические основы проведенных компьютерных экспериментов по подсчету инъективных и сверхрастущих векторов с заданными размерностью и максимальным элементом 16
1.2.2. Алгоритм подсчета возрастающих инъективных векторов 17
1.2.3. Результаты компьютерных экспериментов 21
1.3. Оценки для функций F\ (г, М) и F-2(г. М) 22
1.3.1. Оценка сверху для функции F\ (г, М) 22
1.3.2. Оценка снизу для функции Fi(г, М) 25
1.3.3. Результаты компьютерных экспериментов
1.4. Алгоритм перечисления всех сверхрастущих векторов заданной размерности с фиксированным максимальным элементом 32
1.5. Некоторые особенности сильного модульного умножения 33
1.6. О монотонности функции F\ (г, М) 39
1.7. Выводы 44
2. Модификация метода Лагариаса-Одлыжко решения Задачи о рюкзаке для случая Обобщенной Задачи о рюкзаке и случаев систем задач о рюкзаках 47
2.1. LLL-приведенпые базисы решетки 47
2.2. Алгоритм построения LLL-приведенного базиса решетки 51
2.3. Об оценке числа точек целочисленной решетки, попадающих в сферу малого радиуса в г-мерном пространстве 55
2.4. Метод Лагариаса-Одлыжко решения Задачи о рюкзаке 56
2.5. Метод решения Обобщенной Задачи о рюкзаке, основанный
на методе Лагариаса-Одлыжко 62
2.6. Метод решения систем обобщенных задач о рюкзаках 67
2.7. Метод решения систем задач о рюкзаках 70
2.8. Выводы 74
3. О некоторых свойствах образов трансформированных Задач. LLL-решатель 75
3.1. О верхней границе плотности инъективных векторов 76
3.1.1. О последовательности Штерна и результатах компьютерных экспериментов 76
3.1.2. О плотности инъективных векторов 79
3.2. Некоторые свойства образов трансформированных Задач 86
3.2.1. Задача о точном покрытии ос Задача о рюкзаке 87
3.2.2. Задача о раскрашиваемое ос Задача о рюкзаке 93
3.2.3. Задача 3-ВЫП ос Задача о рюкзаке 95
3.2.4. О коротком сведении Задачи 3-ВЫП к Задаче о рюкзаке 97
3.3. LLL-решатель 101
3.3.1. Конструкция LLL-решателя 101
3.3.2. Результаты компьютерных экспериментов 102
3.4. Выводы 106
Заключение 107
Список использованной литературы
- Математические основы проведенных компьютерных экспериментов по подсчету инъективных и сверхрастущих векторов с заданными размерностью и максимальным элементом
- Алгоритм перечисления всех сверхрастущих векторов заданной размерности с фиксированным максимальным элементом
- Об оценке числа точек целочисленной решетки, попадающих в сферу малого радиуса в г-мерном пространстве
- Некоторые свойства образов трансформированных Задач
Введение к работе
Актуальность темы
Ряд современных систем защиты информации и обеспечения информационной безопасности базируется на NP-полных Задачах. Задачи из класса NP-полных являются, в определенном смысле, «очень сложными» для решения, поэтому, с одной стороны, представляет особый интерес изучение средств и систем защиты информации, для преодоления которых необходимо решить лежащую в их основе NP-полную Задачу, а с другой стороны, методы решения индивидуальных представителей NP-полных Задач представляются естественными методами анализа эффективности разрабатываемых средств и систем защиты информации. Одной из систем защиты информации, в основе которой лежит NP-полная Задача, является асимметричная система шифрования Меркля-Хеллмана, основанная на NP-полной Задаче распознавания - Задаче о рюкзаке. В работах А. Шамира, Е. Брикелля, А. Лагариаса и Дж. Одлыжко по анализу этой системы были предложены методы решения некоторых множеств задач о рюкзаках - индивидуальных представителей вычислительной Задачи о рюкзаке. В диссертационной работе метод решения вычислительной Задачи о рюкзаке, предложенный Дж. Лагариасом и А. Одлыжко, модифицируется в метод решения вычислительной Обобщенной Задачи о рюкзаке и методы решения систем задач о рюкзаках. Кроме того, в диссертационной работе предлагается основанный на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке метод решения за «приемлемое время» представителей NP-полных Задач - LLL-решатель.
Зарождение теории NP-полноты связывают с опубликованной в 1971 году работой С. Кука. В этой работе была установлена важность понятия «полиномиальная сводимость Задач», выделен класс Задач распознавания свойств, которые могут быть решены за полиномиальное время на недетерминированном вычислительном устройстве (недетерминированной машине Тьюринга) (класс NP). Кроме того, было показано, что Задача о выполнимости конъюнктивной нормальной формы представитель класса NP - обладает тем свойством, что любая другая Задача из класса NP может быть сведена к ней за полиномиальное время (то есть в определенном смысле Задача о выполнимости является самой сложной Задачей в классе
NP), и установлено, что таким свойством могут обладать и другие задачи из класса NP (например, Задача о существовании в графе G клики с определенным числом вершин).
Р. Карп, опубликовавший свои результаты вслед за работой С. Кука, показал всю ширину класса «самых трудных» задач из класса NP, получившего название «класс NP-полных Задач». Оказалось, что значительная часть известных комбинаторных Задач (о коммивояжере, о клике, о вершинном покрытии и другие) принадлежит к классу NP-полных.
Одной из рассмотренных Р. Карпом NP-полных Задач была Задача о рюкзаке (распознавания) (также известная как Задача «subset sum» - Задача о сумме элементов подмножества, 0-1 рюкзак), предложенная в 1978 году Р. Мерклем и М. Хеллманом в качестве основы для построения асимметричной системы шифрования.
В работе 1982 года А. Шамир предложил полиномиальный по времени от размерности рюкзачного вектора алгоритм, решающий «практически все» задачи о рюкзаках, рюкзачный вектор которых можно получить с помощью операции сильного модульного умножения из сверхрастущего вектора, способом, предложенным Р. Мерклем и М. Хеллманом для формирования открытых ключей из закрытых в их системе.
Несмотря на то, что А. Шамир показал, что система Меркля-Хеллмана является ненадежной, попытки ее усовершенствования до сих пор не прекращаются, о чем свидетельствуют работы Р. Гудмана и Э. Маколи, X. Hn- деррайтера, Б. Шора и Р. Ривеста, В.О. Осипяна и В.В. Подколзина. Более полный обзор работ в области анализа системы Меркля-Хеллмана и ее развития дан Б. Шнайером.
В 1985 году в работе Дж. Лагариаса и А. Одлыжко был предложен метод решения вычислительной Задачи о рюкзаке, дающий верное решение для «практически всех» задач о рюкзаке, плотность (отношение размерности вектора к двоичному логарифму его максимального элемента) которых не превышает 0,6463..., основанный на сведении вычислительной Задачи о рюкзаке к Задаче вычисления кратчайшего ненулевого вектора решетки. Этот результат был улучшен М. Костером и другимидо плотности, меньшей 0,9408... В диссертационной работе автором рассмотрен вопрос о том, насколько существенны такие ограничения плотности.
Среди методов решения индивидуальных представителей NP-полных Задач за «приемлемое время» наибольшей популярностью, на наш взгляд, на текущий момент обладают методы, предполагающие сведение исходной индивидуальной задачи к задаче выполнимости конъюнктивной нормальной формы (SAT, ВЫП) с последующим решением полученной SAT-задачи с помощью специализированного программного комплекса - SAT-решателя. В этом случае SAT выступает в качестве опорной (базовой) NP-полной Задачи. В основе многих SAT-решателей лежит алгоритм DPLL, разработанный в 1960-1962 годах М. Дэвисом, X. Путманом, Дж. Логеманном и Д. Лавлендом, еще до работ С. Кука и Р. Карпа. Поэтому представляют интерес альтернативные подходы к решению за «приемлемое время» индивидуальных представителей NP-полных Задач. В диссертационной работе предлагается метод решения за «приемлемое время» представителей NP-полных Задач - LLL-решатель, основанный на уже упомянутом методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке. Предлагаемый метод, кроме прочего, интересен тем, что в его основе лежат алгебраические понятия и конструкции, что позволяет привлекать при анализе мощный аппарат этого раздела математики.
Актуальность диссертационной работы определяется теоретической и практической значимостью метода Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке для анализа вновь предлагаемых систем защиты информации, в основе которых лежат задачи рюкзачного типа; теоретической и практической значимостью методов решения индивидуальных представителей NP-полных Задач за «приемлемое время» для информационной безопасности.
Объект исследования
Объектом диссертационного исследования являются NP-полные Задачи, используемые для построения систем защиты информации.
Предмет исследования
Предметом диссертационного исследования являются задачи рюкзачного типа.
Цель работы
Целью диссертационной работы является изучение свойств инъектив- ных и сверхрастугцих векторов, элементы которых являются натуральными числами, и разработка методов решения индивидуальных представителей NP-полных Задач, которые могут быть положены в основу систем защиты информации, основанных на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке.
Для достижения указанной цели в диссертационной работе были поставлены и решены следующие задачи:
-
получить оценки числа инъективных векторов и числа сверхрастущих векторов с заданными размерностью и максимальным элементом;
-
разработать программное обеспечение, позволяющее в параллельном режиме генерировать векторы, элементы которых являются натуральными числами, и определять, принадлежит ли полученный вектор множеству инъективных векторов или множеству сверхрастущих векторов; проанализировать полученные в ходе компьютерных экспериментов данные о числе инъективных векторов и числе сверхрастущих векторов с заданными размерностью и максимальным элементом, сравнить результаты с полученными оценками;
-
изучить свойства операции сильного модульного умножения; разработать программное обеспечение, позволяющее поставить эксперимент по отображению множества инъективных векторов во множество сверхрастущих векторов с помощью сильного модульного умножения;
-
модифицировать метод Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке применительно к случаю вычислительной
Обобщенной Задачи о рюкзаке и случаям, когда нам известно не менее двух задач о рюкзаках, имеющих одинаковое решение (система задач о рюкзаках);
-
получить верхнюю оценку плотности инъективных векторов;
-
разработать программное обеспечение, позволяющее генерировать приведенные задачи о рюкзаках с заданными размерностью вектора и максимальным элементом и решать полученные задачи с помощью метода Лагариаса-Одлыжко; поставить эксперимент по определению доли задач о рюкзаках из заранее определенного множества задач, верно решаемых с помощью метода Лагариаса-Одлыжко;
-
проанализировать возможность решения индивидуальных представителей NP-полных Задач путем сведения их к задачам о рюкзаках и применения к последним метода Лагариаса-Одлыжко.
Области исследований
Областями исследований диссертационной работы являются теория и методология обеспечения информационной безопасности и защиты информации и математические принципы и решения по созданию новых и совершенствованию существующих средств защиты информации и обеспечения информационной безопасности.
Методы исследований
В диссертационной работе использованы аппарат и методы алгебры, комбинаторики, геометрии чисел, теории сложности алгоритмов, математического анализа, теории вычислительного эксперимента, а также методы параллельного и распределенного программирования.
Положения, выносимые на защиту
1. Установлены нижние и верхние оценки для числа сверхрастущих и инъективных векторов, элементы которых являются натуральными числами, с заданными размерностью и максимальным элементом. Показано, что число сверхрастущих и инъективных векторов фиксированной размерности r, элементы которых являются натуральными числами, растет с ростом максимального элемента вектора как полином (r — 1)-ой степени от максимального элемента вектора.
-
-
Разработан эффективный алгоритм перечисления всех сверхрастущих векторов заданной размерности с фиксированным максимальным элементом.
-
Предложены методы решения вычислительной Обобщенной Задачи о рюкзаке и систем задач о рюкзаках, основанные на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке.
-
Предложен подход к решению за «приемлемое время» индивидуальных представителей NP-полных Задач - LLL-решатель. Предложено понятие функции применимости алгоритма к множеству решаемых задач, проведена серия компьютерных экспериментов по вычислению функций применимости LLL-решателя к решению задач о рюкзаках.
-
В результате вычислительных экспериментов, в ходе которых решалось более 20 миллиардов различных задач о рюкзаках малых размерностей (г < 9), было установлено, что характер смещения ветвей функций применимости LLL-решателя с ростом г в случае, если в качестве претендента на вектор, дающий решение задачи о рюкзаке, рассматривается только первый вектор LLL-приведенного базиса, не является равномерным.
-
Установлены верхние и нижние границы для значений элементов bi последовательности Штерна b\ = 1, &2 = 1, = 2, 64 = 3, 65 = б, be = 11, 67 = 20, bg = 40... В предположении, что вектор (ai,..., аг) размерности г ^ 4, элементы которого строятся по следующему правилу:
CL\ = ^r5 а2 = Ьг jT Ьг- 1, . . . , CLr = 'У ^bj,
%=1
является инъективным вектором с наименьшим возможным среди инъективных векторов размерности г максимальным элементом, устанавливается, что плотность din инъективных векторов размерности г ^ 4 удовлетворяет неравенству
d < Г m^r- З-2-i log2([ v^r - 2) + 1/4 - 1/2])'
7. Установлено существование полиномиальной трансформации Задачи 3-ВЫП (распознавания) в Задачу о рюкзаке (распознавания),
при которой образ Задачи 3-ВЫП попадает в область множества задач о рюкзаках с плотностью d < С, где С - любое положительное вещественное число, не превосходящее 3(log27)_1.
Научная новизна
Основные результаты, полученные в работе, являются новыми. Предложенный метод решения индивидуальных представителей NP-полных Задач - LLL-решатель - является новым и достаточно перспективным для включения в перечень существующих в настоящее время средств решения индивидуальных представителей NP-полных Задач за «приемлемое время». Перспективны также новые предложенные методы решения вычислительной Обобщенной Задачи о рюкзаке и систем задач о рюкзаках.
Теоретическая и практическая ценность
Работа носит теоретический характер. Методы, применяемые в этой работе, могут быть использованы при проведении исследований инъективных и сверхрастущих векторов, сложности алгоритмов, методов решения индивидуальных представителей NP-полных Задач.
Практические результаты диссертации также могут найти применение в областях, связанных с решением индивидуальных представителей NP-полных Задач, при разработке и исследовании свойств аппаратно- программных средств защиты информации.
Материал диссертации представляет интерес для специалистов в области дискретной математики, теории сложности алгоритмов и защиты информации. Работа может быть востребована в российских и международных научных центрах, где ведутся исследования, связанные с изучением алгоритмов и их сложности.
Апробация результатов
Основные результаты работы докладывались на научном семинаре, проводимом научно-образовательным центром Ярославского государственного университета им. П.Г. Демидова «Нелинейная динамика», а также на семинарах кафедры компьютерной безопасности и математических методов обработки информации Ярославского государственного университета им.
П.Г. Демидова в 2010-2012 годах, и обсуждались на научных конференциях и выставках научно-технического творчества:
-
-
-
Одиннадцатый Всероссийский конкурс-конференция студентов и аспирантов «Информационная безопасность» SIBINFO-2011, г. Томск, апрель 2011 года;
-
Региональный этап Всероссийской выставки молодых исследователей, изобретателей, рационализаторов «Шаг в будущее», г. Ярославль, ноябрь
-
года;
XII Всероссийская выставка научно-технического творчества молодежи НТТМ-2012, г. Москва, июнь 2012 года;
Международная научная конференция, посвященная 35-летию математического факультета и 25-летию факультета информатики и вычислительной техники Ярославского государственного университета им. П.Г. Демидова, г. Ярославль, март 2012 года;
Международная молодежная конференция-школа «Современные проблемы прикладной математики и информатики», г. Дубна, 22-27 августа
года;
-
11 Всероссийская конференция «Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» - SIBECRYPT'12», г. Иркутск, 3-7 сентября 2012 года;
-
Межрегиональная выставка работ молодых исследователей «Шаг в будущее», г. Ярославль, 1-2 ноября 2012 года.
Исследования по теме диссертационной работы были отмечены дипломом победителя конкурса научно-исследовательских работ студентов вузов Ярославской области 2010 года в области естественных наук, г. Ярославль, 2011 год; дипломом первой степени за первое место в Одиннадцатом Всероссийском конкурсе-конференции студентов и аспирантов «Информационная безопасность» SIBINFO-2011, г. Томск, 2011 год; дипломом за победу во II Внутривузовском конкурсе лучших поисковых научно-исследовательских работ аспирантов «Подготовка научно-педагогических кадров в научно- образовательных центрах ВУЗа» 2011 года по направлению «Информатика», г. Ярославль, 2011 год; дипломом первой степени победителю Регионального этапа Всероссийской выставки молодых исследователей, изобретателей, рационализаторов «Шаг в будущее», г. Ярославль, 2011 год; дипломом лауреата премии по поддержке талантливой молодежи, установленной Указом Президента Российской Федерации от 6 апреля 2006 года № 325 «О мерах государственной поддержки талантливой молодежи»; медалью и дипломом первой степени победителя Межрегиональной выставки работ молодых исследователей «Шаг в будущее» 1-2 ноября 2012 года.
Результаты исследований внедрены и используются в рамках учебного процесса в Ярославском государственном университете им. П.Г. Демидова.
Публикации
Результаты диссертации опубликованы в 9 работах [1-9], из них 5 статей опубликованы в научных журналах, которые включены в перечень российских рецензируемых научных журналов и изданий для опубликования основных научных результатов диссертаций [1-5], 2 статьи — в научных журналах [6,7] и 2 работы — в трудах международных конференций [8,9].
Структура диссертации
Диссертация состоит из введения, трех глав, заключения, списка использованной литературы и приложения. Диссертация содержит 19 рисунков, 16 таблиц. Общий объем диссертации составляет 116 страниц.
Соответствие паспорту специальности
Тема и содержание диссертационного исследования соответствует требованиям паспорта специальности 05.13.19 «Методы и системы защиты информации, информационная безопасность» и соответствует следующим областям исследований паспорта специальности: 1. Теория и методология обеспечения информационной безопасности и защиты информации; 13. Принципы и решения (технические, математические, организационные и др.) по созданию новых и совершенствованию существующих средств защиты информации и обеспечения информационной безопасности.
Личный вклад автора
Все результаты, выносимые на защиту, получены автором лично.
Благодарности
Автор выражает благодарность своему научному руководителю доктору физико-математических наук, профессору Валерию Георгиевичу Дурневу за постановку задач и постоянное внимание к работе, а также Александру Васильевичу Черемушкину за внимание к работе и ценные замечания.
Математические основы проведенных компьютерных экспериментов по подсчету инъективных и сверхрастущих векторов с заданными размерностью и максимальным элементом
В 1982 году А. Шамир [47] показал, что система Меркля-Хеллмана не является надежной. Но несмотря на то, что с тех пор эта система стала классической и включена во многие учебные пособия [7.17,19.20], при изложении вопросов, связанных с рюкзачной системой Меркля-Хеллмана, ограничиваются общим описанием принципов ее функционирования и механизма одной из известных атак - либо атаки А. Шамира. либо атаки Лагариаса-Одлыжко, при этом вопрос об изучении свойств сильного модульного умножения, выбранного в качестве запутывающего преобразования в системе Меркля-Хеллмана. не ставится.
Прежде чем обратиться к вопросу о свойствах сильного модульного умножения, необходимо для начала понять, какое место занимают инъек-тивиые и сверхрастушие векторы среди всех возможных векторов с натуральными элементами. Поскольку в известной автору литературе вопрос о числе ипъективных и сверхрастущих векторов заданной размерности не ставится, автору показатось разумным рассмотреть этот вопрос и начать исследования с непосредственного численного подсчета этих векторов.
Обозначим через VJ„(r. М) множество инъективных векторов размерности г с максимальным элементом, равным М; Vyjn(r, М) - множество возрастающих инъективных векторов размерности г с максимальным элементом, равным М; Vfg(r. М) - множество сверхрастущих векторов размерности г с максимальным элементом, равным М. Утверждение 3. Ут(г, М)\ = г! \Vg-m{r.M)\. Доказательство. Утверждение 3 справедливо, поскольку свойство инъек-тивности не зависит от порядка следования элементов вектора и все элементы инъективного вектора обязательно различны.
Предлагаемый автором алгоритм подсчета возрастающих инъективных векторов размерности г + 1 с фиксированным максимальным элементом ar_i = М состоит из двух блоков. Первый блок алгоритма реализует r-разрядный счетчик по элемен там а.\ аг. Если инициализация алгоритма осуществляется вектором (ai... ..ak). то первый блок алгоритма отвечает за последовательное .увеличение a,k на единицу до тех пор, пока значение а& не достигнет М — r + k (по утверждению 5 М — г + к является предельным значением элемента ад-нри 1 к г), после чего при к 1 происходит увеличение на единицу элемента а -ь а элемент о.д; переинициализируется значением a _i + 1. а при к = 1 алгоритм заканчивает работу. Далее процедура повторяется до достижения элементом ak-i значения М — г 4- к — 1 и так далее. Второй блок отвечает за проверку вектора (oj,..., а&) на инъективпость. Ввиду следствия 1 при каждом изменении элемента од- необходимо убедиться. что вектор (ai....,cik) является ииъективным, поскольку в противном случае любой построенный вектор (о1;..., o,/r. а.д;+і, ..., ат+і) не будет ииъективным и не будет влиять на результаты подсчета, поэтому в его построении нет необходимости. Если вектор (а\,... , ад-) оказался неипъективным. необходимо увеличить о д. на 1 и повторить процедуру проверки на инъек-тнвность. Этот процесс необходимо продолжать до тех пор. пока (аг,..., ак) не станет инъективиым или ад. не достигнет значения М — г + к. Если установлено. что вектор (o-i,... .од-) - инъективный, то переходим к элементу од._і; инициализируем его значением од- + 1 и будем добиваться инъектив-постн вектора (оі;... .од-і) описанным выше способом. Если проверку на инъективность проходит вектор (оі,....ог), то проверяется на инъективпость вектор (аь .... ar. М), и если он оказывается ииъективным, то счетчик возрастающих инъективпых векторов размерности г + 1 с фиксированным максимальным элементом, равным М, увеличивается на 1.
Проверка ипъективности вектора осуществляется с помощью следующей процедуры. Пусть (oi,... .ад_і) - инъективный вектор, и все возможные 2к 1 — 1 значения (за исключением 0) суммы X =i eiaJ- где e:i е (0 1} для всех 1 j к — 1. записаны в целочисленный массив SUMS[A; — 1] в порядке возрастания. Необходимо проверить, является ли инъективиым вектор (oj,... ,о.д.). Сформируем новый массив SUMS[A;] размерности 2к — 1 следующим образом: начальные 2fc_1 — 1 элементов массива SUMS [/г] - это элементы массива SUMS [А; — 1], элементом массива SUMS [А;] под номером 2к 1 становится ад . а оставшиеся элементы представляют собой суммы о,д- и каждого из 2А" 1 — 1 элементов массива SUMS [А; — 1]. Таким образом, в массиве SUMS [А:] оказываются записанными все возможные 2к — 1 значения (за исключением 0) суммы J2j=\ ejai- где ei е {0-. 1} Для всех 1 J к, причем для первых 2к 1 — 1 элементов массива SUMS[fc] ед- = 0, а для остальных ек = 1.
Упорядочим массив SUMS[A:] по возрастанию и проверим, не встречаются ли в нем одинаковые элементы (эта задача может быть решена в процессе сортировки, но для наглядности в описании алгоритма сортировка и поиск совпадений выполняются последовательно, кроме того, сортировка может осуществляться при формировании массива SUMS [А;]). Если одинаковые элементы встретились, то вектор (о.],..., ад,.) - неинъективный (нашлись различные подмножества элементов вектора, обладающие одинаковыми суммами элементов). Иначе вектор (сц,..., ад-) - инъективный. Для описания процедур и алгоритмов используется псевдокод, который напоминает известные языки программирования (Pascal. С). Описание некоторых шагов процедур и алгоритмов дается на неформальном языке.
Алгоритм перечисления всех сверхрастущих векторов заданной размерности с фиксированным максимальным элементом
Таким образом, для инъективного отображения SSMUrjj правомерно ставить вопросы о плотности (полноте) покрытия множества Vgm(r. М) элементами образа SSMU, _v(V/9(r. л/)), а также о равномерности этого покрытия.
Для проведения компьютерных экспериментов но изучению равномерности покрытия множества V(J,„(r. М) элементами образа SSMU, м(У}д{г. М)) автором использовались описанные ранее алгоритмы построения возрастающих инъективных векторов и сверхрастущпх векторов с заданными размерностью и максимальным элементом.
Компьютерные эксперименты состоят в следующем. Для заданных параметров размерности вектора г и натурального числа М генерируются множества Vjg(r. М) и Vgin(r. М). С каждым элементом из множества Vgi11(r. AI) связывается уникальный счетчик (показатели всех счетчиков обнуляются). Затем для каждого вектора А — (аІ ..... я,) Є V/g(r. М) рассматриваются все возможные модули из интервала (5 j=1a,.min(2 Yl[=i ai- 0L a -Для каждого модуля - все возможные множители 1 t т такие, что (t.m) = 1. Для каждой тройки (A.m.t) из вектора А с помощью операции сильного модульного умножения относительно модуля т и множителя t получается вектор В = (Ь\,..., Ьг). элементы которого упорядочиваются по возрастанию. Связанный с полученным возрастающим вектором счетчик увеличивается па 1. Эксперимент закончен после того, как исчерпаны все возможности для выбора нового вектора А.
Для различных троек (A.m.t) (сверхрастуший вектор, модуль, множитель) векторы, полученные с помощью операции сильного модульного умножения относительно модуля т и множителя t из вектора А с последующей сортировкой элементов полученного вектора по возрастанию, могут совпа дать. Например, это выполнено для следующих двух троек: ((1. 2, 6), 17, 3) и ((1. 2, 4). 11, 3) - им соответствует вектор (1, 3, 6).
Определение 5. Для, вектора В размерности г число троек (А = ( 2i,..., ar).m,t) таких, что т Є ( [=1ay;,min(2 =1 а,;, А/)]. 1 t т. (t. т) = 1 и В = SORT((ta\. mod m). (ta-2: mod m),.... (iar, mod m)), где SORT - процедура сортировки элементов вектора по возрастанию, назовем числом представлений ветпора В.
Введем в рассмотрение функцию плотности F(r, М) с областью определения № - ее значения суть отношение числа векторов из VgjV (г. М), число представлений которых больше 0. к общему числу элементов множества Vgjn{r. M).
Проведенные вычислительные эксперименты, результаты которых приведены на рисунке 8, позволяют выдвинуть следующую гипотезу. Гипотеза 1. При фиксированном г Є N F(r,M) достигает 0.9 при значениях М. близких к 22г 2. Под «достижением» в гипотезе 1 понимается, что существует такое М\ є N. близкое к 22г_2. что F(r, Mi) 0.9, по при этом могут существовать такие М Ми что F{r,M) 0,9.
В результате компьютерных экспериментов, реализованных с применением технологий параллельного и распределенного программирования. проводившихся но описанным выше схемам, было установлено, что при 2 г 4 F(r. М) достигает 0,9 при М = 22г"2 + 2Г - 1.
В ходе проведения компьютерных экспериментов автором было установлено. что при г G покрытие множества Vgjn(r. М) элементами образа SSMUT.\i(Vfg{r. М)) не является равномерным.
На рисунках 9-12 приведены результаты одного из экспериментов для г = 3 и М = 34. На рисунках каждому натуральному числу на оси От (носящей в разных случаях названия Ln. Sum. Id) соответствует возрастающий ипъективный вектор. Для оси Id векторы расположены в лексикографическом порядке по возрастанию. Меньшим натуральным числам для оси Sum соответствуют векторы с меньшей суммой элементов, для оси Мах - векторы с меньшим максимальным элементом, для оси Ln - векторы с меньшей евклидовой длиной. В кластерах векторов с одинаковыми параметрами (сумма элементов, максимальный элемент, евклидова норма) векторы упорядочены в лексикографическом порядке по возрастанию. По оси Representation number отложено число представлений соответствующего возрастающего инъектнвиого вектора.
Число представлений возрастающих инъективных векторов при г = З, М = 34 Обратим внимание на характерный график «пилы» на рисунке 9. При ближайшем рассмотрении каждый се «зубчик» становится схож со всем графиком. то есть также имеет пилообразную форму. Наблюдаемые на графике значительные скачки соответствуют переходу от а\ = і к а і = і + 1 для 1 г 31. Соответственно при переходе к «зубчику» наблюдаются те же скачки при переходе от а2 = г к о = і + 1 для 2 і 32 и так далее, так что график обладает определенным свойством самоподобия. Representation number
Эта особенность связана с вопросом о разбиениях числа М, более точно -с вопросом о том, сколько существует представлений числа М в виде суммы М = Y Z\ ai нз г_"1 различных слагаемых a-i таких, что вектор [а\...., ar_i) является возрастающим и инъективпым.
Определение 6. Инъективпым г-представлением числа М назовем его представление в виде такой суммы М = Yl -iZi a?; что вектор (а\...., ar_i) является возрастающим инъективпым вектором.
Если у натурального числа М + 1 количество ииъективпых г-представлений значительно больше, чем у числа М, то Fi(r, М) F] (г, М + 1). В таблицах 4-12 приведены результаты исследования ииъективпых 5-представлспий для чисел 13 М 21, в столбце Inj которых знаком «—» помечены инъективные векторы. Исходя из гипотезы о том. что число возрастающих ииъективпых векторов с a,._i М и число возрастающих инъектпвных векторов с о.Т-\ М не должны сильно различаться, придем к выводу, что значительную разницу между числом возрастающих ииъективпых векторов вида могут внести только «запреты» на использование некоторых возрастающих инъектпвных векторов вида (ai.a-2,.... ftr-i) в качестве начальных. Число этих «запретов» определяется числом ииъективпых г-представлений для чисел М и М + 1. Из таблиц 4 -12 видно, что в случае г = 5 число ииъективпых г-нредставлений четных чисел значительно уступает числу ииъективпых r-представлєний соседних с ними нечетных чисел, что и приводит к немонотонности функции Fj(r, М).
Замечание о числе представлении небольших натуральных чисел в виде суммы трех простых чисел, образующих инъективный вектор
В середине XVIII века немецкий математик К. Гольдбах выдвинул в письме Л. Эйлеру гипотезу о том, что каждое нечетное число, превосходящее 5. можно представить в виде суммы трех простых необязательно различных чисел. Эта гипотеза получила название «тернарная проблема Гольдбаха». Гипотеза оставалась долгое время не доказанной, хотя и привлекала к себе внимание многих математиков. В 1923 году Г. Харди и Дж. Литлвуд показали [35]. что тернарная проблема Гольдбаха для достаточно больших
Об оценке числа точек целочисленной решетки, попадающих в сферу малого радиуса в г-мерном пространстве
Обозначим через S,.(R) число точек целочисленной решетки, попавших внутрь или на поверхность r-мерной сферы радиуса VR с центром в начале координат (в /--мерном пространстве).
Задача оценки числа точек целочисленной решетки, попадающих в г-мерную сферу, восходит к работам К. Гаусса [14]. При достаточно больших R. число точек целочисленной решетки, попадающих в r-мерную сферу. близко к величине объема сферы Vr(R) с ошибкой, пропорциональной площади поверхности этой сферы Ar(R) [14]. Поскольку где T(z) - Гамма-функция, то Vr(R) » AV{R) для достаточно больших R. но если R мало, то это неверно. Кроме того, при малых R число точек целочисленной решетки, попадающих в сферу, сильно зависит от того, где расположен ее центр [39].
Теорема 6 дает оценку числа точек целочисленной решетки, попадающих в сферу радиуса у/аг. где параметр а 0 - некоторое вещественное число, с центром в начале координат. Теорема 6 представляет собой некоторое обобщение теоремы 3.2 работы [43]. в которой рассматривался случай т = 2. Далее в этой работе будут рассматриваться случаи а = Щ - и а = mj . где натуральное число т 2.
Заметим, что необходимо рассмотреть только случаи 1 S Xw=i аь так как тривиальные случал S = 0 и S = Yli=i а легк определяются и не представляют интереса. В работе [43] вводится следующая характеристика задачи о рюкзаке с вектором А = (аьо.2,... ,аг) Є W, называемая плотностью задачи о рюкзаке.
Плотностью задачи о рюкзаке с вектором А = (о-і; 0.9,..., от) є N r называется число Iog2(maxi /O.o.,) Понятие плотности задачи о рюкзаке восходит к терминологическому контексту, существующему в сфере информационной безопасности. Напри мер. для системы Меркля-Хеллмана значение отношения -,—-,— г близ ко к отношению числа бит исходного открытого сообщения к среднему числу бит зашифрованного текста, отсюда и наименование характеристики «плотность».
Дж. Л агар н ас и А. Одлыжко в работе [43] предложили для решения рассматриваемой Задачи о рюкзаке следующий метод, основанный па сведении задачи о рюкзаке к задаче поиска, короткого вектора в решетке специального вида.
В целях обоснования действенности предложенного метода Дж. Лагари-ас и А. Одлыжко ставят вопрос о том, какую долю задач из определенного множества L(B, е) может решать (то есть выдавать на них верный ответ) предложенный метод.
Пусть уравнение (8) имеет особенное зафиксированное решение (еі.....ег) є {0,1}г, причем 1 Y i=iei г — 1; чт0 исключает случаи S = 0 и S = "%2 i-i cij. Положим вектор є равным (еі,..., ег. 0) и определим множество L(B,e) как множество, содержащее все решетки A(A,S), задаваемые системой векторов (9), для которых выполнены следующие условия:
Во множестве L(B.e) с каждым вектором А. удовлетворяющим условию (10). ассоциирована одна решетка A(A,S), поэтому во множество L(B, е) входят ровно В решеток. Зафиксированный вектор е содержится в каждой решетке из множества L(B,e). так как из соотношения (11) и построения линейно независимых векторов &1,.... 6r+i (9) следует:
Следующая далее теорема 7 [43] утверждает, что для «практически всех» решеток из множества L(B, в) при условии, что В 2С Г, где константа CQ = 1.54725..., вектор е является кратчайшим. Отметим, что условие В 2С{)Г эквивалентно ограничению плотности рассматриваемых задач о рюкзаке (ізр 0,6463...
Теорема 7. Пусть є є {0,1}г+1 - вектор размерности г + 1. для которого ег+і = 0 и Yl i=\ ei 9- Тогда если В = 2;3г для некоторого р Со, где константа Со = 1,54725..., то число решеток К в L(B,e). для. которых е не является кратчайшим ненулевым вектором в Л. есть
Предположим, что имеется алгоритм «Оракул», который за полиномиальное время выдает один из кратчайших (самых коротких) ненулевых векторов решеток некоторых специальных видов (например, решеток, заданных наборами векторов (9), другие виды решеток будут описаны далее), тогда теорема 7 утверждает, что с помощью алгоритма «Оракул» можпо найти вектор-решение задачи о рюкзаке е для «практически всех» решеток из множества Ь(В. е) при условии, что плотности рассматриваемых задач о рюкзаке (ізр 0,6463...
Несмотря на то. что Задача нахождения кратчайшего ненулевого вектора решетки в общем случае является КР-трудной [3,23]. ответ на вопрос о существовании алгоритма «Оракул», возможно вероятностного, неизвестен, при реализации «приближением» к этому алгоритму служит алгоритм построения LLL-приведешюго базиса решетки, позволяющий за полиномиальное время получать «достаточно короткие» векторы [9,38].
После первой работы Дж. Лагариаса и А. Одлыжко [43] методы доказательства введенных ими теорем совершенствовались, определенный итог этой работе был подведен М. Костером и другими в работе [30].
Некоторые свойства образов трансформированных Задач
Напомним формулировки рассматриваемых в этой главе Задал распознавания. за исключением Задачи о рюкзаке, рассмотренной в главе 1. Задача 3-ВЫП. Условие: Дана булева, формула F в 3-КНФ. Вопрос: Выполнима ли булева формула F? Задача о раскрашиваемости. Условие: Даны неориентированный граф G = (V. Е) и натуральное число к. Вопрос: Является ли граф G к-раскрашиваемым? Задача о точном покрытии. Условие: Дано семейство подмножеств М = {М\,.... Mi} множества К = {щ,...,ир}. Вопрос: Существует ли для семейства М подсемейство попарно непересекающихся множеств, являющееся покрытием множества U? Напомним некоторые определения.
Определение 21. Под массовой Задачей будем понимать бесконечную серию (мноэюеетво) однотипных индивидуальных задач, зависящих от некоторого параметра [6].
Определение 22. Пусть Ау и A-i - Задачи распознавания. Будем говорить. что Задача А\ полиномиально преобразуется (трансформируется. вкладывается) в Задачу Ао, если по произвольной данной строке х можно за полиномиальное (относительно ее длины) время построить такую строку у, что х является индивидуальной задачей Задачи А\ с ответом «Да» тогда и только тогда, когда у является, индивидуальной задачей Задачи А-2 с ответом «Да». Далее рассматриваются вопросы о том. в какую область множества задач о рюкзаках (относительно плотности) попадают при полиномиальной трансформации образы NP-полпых Задач распознавания 3-ВЫП, Раскра-шиваемость, Точное покрытие, и какая доля задач из образа попадает в область множества задач о рюкзаках с плотностью меньше, чем 0,9408...
Пусть семейство подмножеств М = {М\.... .Mj] множества U = {щ.... .ир} определяет Задачу о точном покрытии, тогда Задача о точном покрытии может быть вложена в Задачу о рюкзаке с помощью следующего преобразования Т\ [36].
Справедлива следующая теорема, для которой дается доказательство, основанное на арифметических соображениях. В первоисточнике [36] доказательство было опущено.
Утверждение 12. Преобразование Т\ является полиномиальной трансформацией Задачи о точном покрытии в Задачу о рюкзаке.
Покажем, что задача о рюкзаке (а\,..., щ, S). определенная преобразованием Ті, имеет решение тогда и только тогда, когда для семейства М найдется подсемейство попарно непересекающихся множеств, являющееся покрытием множества Ы.
Предположим вначале, что для семейства М нашлось подсемейство Ф попарно непересекающихся множеств, являющееся покрытием множества U. и рассмотрим сумму
Поскольку подсемейство Ф является точным покрытием, то Yl\j і м єФ} iJ Иначе если существует индекс 1 г р такой, 4X0 ll{j\M \eiJ = T0 ui U-- ш u & Уц\м3еФ}Щ, и тогда Ф не является покрытием, а если существует индекс 1 г р такой, что J2\j\ м еФ}и 1; то найдутся множества А/д Є Ф и М,о Є Ф такие, что и І є Щ П Mj2, и тогда Ф не является точным покрытием. Поэтому
Если е = 1, то полагаем, что М,- входит в подсемейство попарно непересекающихся множеств, образующее покрытие множества U. Покажем, что таким образом получается точное покрытие. Сначала предположим, что найдется элемент щ Є U такой, что щ и/;=1е М7-. тогда YLj=ieiEkj = 0 - противоречие. Теперь предположим, что найдутся множества Mj\ и Mj2 такие, что eji = е/2 = 1, и найдется элемент г//,- Є U такой, что щ Є А/д и щ. є Mj-2. тогда J2j=i ejkj 2 - противоречие.
Отметим, что вопрос о вхождении элемента ир в одно из множеств семейства М может быть решен за 0(1р) арифметических операций. Если ир не входит ни в одно множество семейства М, то для семейства М подсемейства попарно непересекающихся множеств, являющегося покрытием множества U. не существует. Далее рассматриваются случаи, для которых элемент ир входит, но крайней мере, в одно из множеств семейства А/.
Утверждение 13. При полиномиальной трансформации Т\ Задачи о точном покрытии в Задачу о рюкзаке образ задач о тючном покрытии, удовлетворяющих условию
лежит в области множества задач о рюкзаках, при решении которых с помощью алгоритма «Оракул» вероятность получения неверного от.вета стремится к нулю при условии, что размерность задачи стремится к бесконечности.
Доказательство. Кривая р = Ъо \ + 1, где С і = 0 94Q8 , делит положительный квадрант плоскости 0,9408... на две области (рисунок 1С). Область над кривой соответствует значениям функции F(p, I), меньшим 0,9408... (задачи о точном покрытии с параметрами р, I из дайной области трансформируются в задачи о рюкзаках, которые с высокой степенью вероятности должны решаться с помощью алгоритма «Оракул»), назовем эту область «хорошей». Область под кривой соответствует значениям функции F(p.l), большим 0,9408..., назовем эту область «плохой».
Кроме того, заметим, что так как у каждого подмножества множества U есть дополнение до множества U. и ввиду нецелесообразности включения в семейство М пустого множества и наличия тривиального решения задачи о точном покрытии в случае, если U Є М. можно считать, что в семейство М входят не более чем 2?, 1 — 1 множеств. Иными словами. / 2Р 1 — 1 или \og2(l + 1) р— 1. и «плохая» область, на самом деле, оказывается еще более урезанной.
Похожие диссертации на Компьютерно-аналитическое исследование задач рюкзачного типа как средство анализа и совершенствования систем защиты информации
-
-
-
-
