На правах рукописи

Мурин Дмитрий Михайлович

Компьютерно-аналитическое исследование

задач рюкзачного типа

как средство анализа и совершенствования

систем защиты информации

05.13.19 – Методы и системы защиты информации,

информационная безопасность

Автореферат

диссертации на соискание ученой степени кандидата

физико-математических наук

Томск – 2013

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Ярославский государственный университет им. П.Г. Демидова на кафедре компьютерной безопасности и математических методов обработки информации.

Научный руководитель: доктор физико-математических наук, профессор Дурнев Валерий Георгиевич

Официальные оппоненты:

Горшков Сергей Павлович, доктор физико-математических наук, войсковая часть № 71330–А, сотрудник Старченко Александр Васильевич, доктор физико-математических наук, профессор, федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Национальный исследовательский Томский государственный университет, кафедра вычислительной математики и компьютерного моделирования, заведующий кафедрой

Ведущая организация: Федеральное государственное автономное образовательное учреждение высшего профессионального образования Уральский федеральный университет имени первого Президента России Б.Н.Ельцина, г. Екатеринбург

Защита состоится 3 сентября 2013 г. в 9 часов 00 минут на заседании диссертационного совета Д 212.267.22, созданного на базе федерального государственного бюджетного образовательного учреждения высшего профессионального образования Национальный исследовательский Томский государственный университет, по адресу: 634050, г. Томск, пр. Ленина, 36 (корпус № 2, аудитория 212б).

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета.

Автореферат разослан 23 июля 2013 г.

Ученый секретарь Тренькаев диссертационного совета Вадим Николаевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы Ряд современных систем защиты информации и обеспечения информационной безопасности базируется на NP-полных Задачах. Задачи из класса NP-полных являются, в определенном смысле, очень сложными для решения, поэтому, с одной стороны, представляет особый интерес изучение средств и систем защиты информации, для преодоления которых необходимо решить лежащую в их основе NP-полную Задачу, а с другой стороны, методы решения индивидуальных представителей NP-полных Задач представляются естественными методами анализа эффективности разрабатываемых средств и систем защиты информации. Одной из систем защиты информации, в основе которой лежит NP-полная Задача, является асимметричная система шифрования Меркля-Хеллмана, основанная на NP-полной Задаче распознавания – Задаче о рюкзаке. В работах А. Шамира, Е. Брикелля, А. Лагариаса и Дж. Одлыжко по анализу этой системы были предложены методы решения некоторых множеств задач о рюкзаках – индивидуальных представителей вычислительной Задачи о рюкзаке. В диссертационной работе метод решения вычислительной Задачи о рюкзаке, предложенный Дж. Лагариасом и А. Одлыжко1, модифицируется в метод решения вычислительной Обобщенной Задачи о рюкзаке и методы решения систем задач о рюкзаках. Кроме того, в диссертационной работе предлагается основанный на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке метод решения за приемлемое время представителей NP-полных Задач – LLL-решатель.

Зарождение теории NP-полноты связывают с опубликованной в 1971 году работой С. Кука. В этой работе была установлена важность понятия полиномиальная сводимость Задач, выделен класс Задач распознавания свойств, которые могут быть решены за полиномиальное время на недетерминированном вычислительном устройстве (недетерминированной машине Тьюринга) (класс NP). Кроме того, было показано, что Задача о выполнимости конъюнктивной нормальной формы – представитель класса NP – обладает тем свойством, что любая другая Задача из класса NP может быть сведена к ней за полиномиальное время (то есть в определенном смысле Задача о выполнимости является самой сложной Задачей в классе Odlyzko A.M., Lagarias J.C. Solving Low-Density Subset Sum Problems // Journal of the Association for Computing Machinery. 1985. vol. 32, № 1. p. 229–246.

NP), и установлено, что таким свойством могут обладать и другие задачи из класса NP (например, Задача о существовании в графе G клики с определенным числом вершин).

Р. Карп, опубликовавший свои результаты вслед за работой С. Кука, показал всю ширину класса самых трудных задач из класса NP, получившего название класс NP-полных Задач. Оказалось, что значительная часть известных комбинаторных Задач (о коммивояжере, о клике, о вершинном покрытии и другие) принадлежит к классу NP-полных.

Одной из рассмотренных Р. Карпом NP-полных Задач была Задача о рюкзаке (распознавания) (также известная как Задача subset sum – Задача о сумме элементов подмножества, 0-1 рюкзак), предложенная в году Р. Мерклем и М. Хеллманом в качестве основы для построения асимметричной системы шифрования.

';

В работе 1982 года А. Шамир2 предложил полиномиальный по времени от размерности рюкзачного вектора алгоритм, решающий практически все задачи о рюкзаках, рюкзачный вектор которых можно получить с помощью операции сильного модульного умножения из сверхрастущего вектора, способом, предложенным Р. Мерклем и М. Хеллманом для формирования открытых ключей из закрытых в их системе.

Несмотря на то, что А. Шамир показал, что система Меркля-Хеллмана является ненадежной, попытки ее усовершенствования до сих пор не прекращаются, о чем свидетельствуют работы Р. Гудмана и Э. Маколи3, Х. Нидеррайтера4, Б. Шора и Р. Ривеста5, В.О. Осипяна и В.В. Подколзина6. Более полный обзор работ в области анализа системы Меркля-Хеллмана и ее развития дан Б. Шнайером7.

Shamir A. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem // Proceedings of the 23rd FOCS Symposium. 1982. p. 145–152.

Goodman R., McAuley A. A new trapdoor knapsack public-key cryptosystem // IEE PROCEEDINGS.

1985. Vol. 132, № 6. p. 289–292.

Niederreiter H. Knapsack-Type Cryptosystems and Algebraic Coding Theory // Problems of Control and Information Theory. 1986. № 15(2). p. 159-166.

Chor B., Rivest R. A knapsack-type public key cryptosystem based on arithmetic in nite elds // In Advances in Cryptology CRYPTO’84, LNCS, Springer-Verlag. 1985. p. 54–65.

Осипян В.О. О криптосистемах с заданным рюкзаком // Материалы VI Международной научнопрактической конференции Информационная безопасность. Таганрог: Изд-во ТРТУ. 2004. С. 269–271.

Осипян В.О. О системе защиты информации на основе проблемы рюкзака // Известия Томского политехнического университета. 2006. Т. 309. № 2. С. 209–212.

Подколзин В.В., Осипян В.О. Об одном методе определения верхней границы числа входов для рюкзачных систем защиты информации // Вестник Воронежского института МВД России. 2010. № 4.

С. 83–90.

Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си.

М.: Триумф, 2002. 816 с.

В 1985 году в работе Дж. Лагариаса и А. Одлыжко8 был предложен метод решения вычислительной Задачи о рюкзаке, дающий верное решение для практически всех задач о рюкзаке, плотность (отношение размерности вектора к двоичному логарифму его максимального элемента) которых не превышает 0,6463..., основанный на сведении вычислительной Задачи о рюкзаке к Задаче вычисления кратчайшего ненулевого вектора решетки. Этот результат был улучшен М. Костером и другими до плотности, меньшей 0,9408... В диссертационной работе автором рассмотрен вопрос о том, насколько существенны такие ограничения плотности.

Среди методов решения индивидуальных представителей NP-полных Задач за приемлемое время наибольшей популярностью, на наш взгляд, на текущий момент обладают методы, предполагающие сведение исходной индивидуальной задачи к задаче выполнимости конъюнктивной нормальной формы (SAT, ВЫП) с последующим решением полученной SAT-задачи с помощью специализированного программного комплекса – SAT-решателя10.

В этом случае SAT выступает в качестве опорной (базовой) NP-полной Задачи. В основе многих SAT-решателей лежит алгоритм DPLL, разработанный в 1960–1962 годах М. Дэвисом, Х. Путманом, Дж. Логеманном и Д. Лавлендом, еще до работ С. Кука и Р. Карпа. Поэтому представляют интерес альтернативные подходы к решению за приемлемое время индивидуальных представителей NP-полных Задач. В диссертационной работе предлагается метод решения за приемлемое время представителей NP-полных Задач – LLL-решатель, основанный на уже упомянутом методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке.

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

Актуальность диссертационной работы определяется теоретической и практической значимостью метода Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке для анализа вновь предлагаемых систем защиты информации, в основе которых лежат задачи рюкзачного типа; теоретической и практической значимостью методов решения индивидуальных Odlyzko A.M., Lagarias J.C. Solving Low-Density Subset Sum Problems. p. 229–246.

Coster M.J., Joux A., LaMacchia B.A., Odlyzko A.M., Schnorr C.-P., Stern J. Improved low-density subset sum algorithms // Computational Complexity. 1992. № 2. p. 111–128.

Goldberg E., Novikov Y. BerkMin: A fast and robust SAT-solver // In Design, Automation, and Test in Europe. 2002. p. 142–149.

Moskewicz M., Madigan C., Zhao Y., Zhang L., Malik S. Cha: Engineering an Ecient SAT Solver // In Proc. 38th Design Automation Conference. 2001. p. 530– представителей NP-полных Задач за приемлемое время для информационной безопасности.

Объект исследования Объектом диссертационного исследования являются NP-полные Задачи, используемые для построения систем защиты информации.

Предмет исследования Предметом диссертационного исследования являются задачи рюкзачного типа.

Цель работы Целью диссертационной работы является изучение свойств инъективных и сверхрастущих векторов, элементы которых являются натуральными числами, и разработка методов решения индивидуальных представителей NP-полных Задач, которые могут быть положены в основу систем защиты информации, основанных на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке.

Для достижения указанной цели в диссертационной работе были поставлены и решены следующие задачи:

1) получить оценки числа инъективных векторов и числа сверхрастущих векторов с заданными размерностью и максимальным элементом;

2) разработать программное обеспечение, позволяющее в параллельном режиме генерировать векторы, элементы которых являются натуральными числами, и определять, принадлежит ли полученный вектор множеству инъективных векторов или множеству сверхрастущих векторов; проанализировать полученные в ходе компьютерных экспериментов данные о числе инъективных векторов и числе сверхрастущих векторов с заданными размерностью и максимальным элементом, сравнить результаты с полученными оценками;

3) изучить свойства операции сильного модульного умножения; разработать программное обеспечение, позволяющее поставить эксперимент по отображению множества инъективных векторов во множество сверхрастущих векторов с помощью сильного модульного умножения;

4) модифицировать метод Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке применительно к случаю вычислительной Обобщенной Задачи о рюкзаке и случаям, когда нам известно не менее двух задач о рюкзаках, имеющих одинаковое решение (система задач о рюкзаках);

5) получить верхнюю оценку плотности инъективных векторов;

6) разработать программное обеспечение, позволяющее генерировать приведенные задачи о рюкзаках с заданными размерностью вектора и максимальным элементом и решать полученные задачи с помощью метода Лагариаса-Одлыжко; поставить эксперимент по определению доли задач о рюкзаках из заранее определенного множества задач, верно решаемых с помощью метода Лагариаса-Одлыжко;

7) проанализировать возможность решения индивидуальных представителей NP-полных Задач путем сведения их к задачам о рюкзаках и применения к последним метода Лагариаса-Одлыжко.

Области исследований Областями исследований диссертационной работы являются теория и методология обеспечения информационной безопасности и защиты информации и математические принципы и решения по созданию новых и совершенствованию существующих средств защиты информации и обеспечения информационной безопасности.

Методы исследований В диссертационной работе использованы аппарат и методы алгебры, комбинаторики, геометрии чисел, теории сложности алгоритмов, математического анализа, теории вычислительного эксперимента, а также методы параллельного и распределенного программирования.

Положения, выносимые на защиту 1. Установлены нижние и верхние оценки для числа сверхрастущих и инъективных векторов, элементы которых являются натуральными числами, с заданными размерностью и максимальным элементом. Показано, что число сверхрастущих и инъективных векторов фиксированной размерности r, элементы которых являются натуральными числами, растет с ростом максимального элемента вектора как полином (r 1)-ой степени от максимального элемента вектора.

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

3. Предложены методы решения вычислительной Обобщенной Задачи о рюкзаке и систем задач о рюкзаках, основанные на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке.

4. Предложен подход к решению за приемлемое время индивидуальных представителей NP-полных Задач – LLL-решатель. Предложено понятие функции применимости алгоритма к множеству решаемых задач, проведена серия компьютерных экспериментов по вычислению функций применимости LLL-решателя к решению задач о рюкзаках.

5. В результате вычислительных экспериментов, в ходе которых решалось более 20 миллиардов различных задач о рюкзаках малых размерностей (r < 9), было установлено, что характер смещения ветвей функций применимости LLL-решателя с ростом r в случае, если в качестве претендента на вектор, дающий решение задачи о рюкзаке, рассматривается только первый вектор LLL-приведенного базиса, не является равномерным.

6. Установлены верхние и нижние границы для значений элементов bi последовательности Штерна b1 = 1, b2 = 1, b3 = 2, b4 = 3, b5 = 6, b6 = 11, b7 = 20, b8 = 40... В предположении, что вектор (a1,..., ar ) размерности r 4, элементы которого строятся по следующему правилу:

является инъективным вектором с наименьшим возможным среди инъективных векторов размерности r максимальным элементом, устанавливается, что плотность din инъективных векторов размерности r 4 удовлетворяет неравенству 7. Установлено существование полиномиальной трансформации Задачи 3-ВЫП (распознавания) в Задачу о рюкзаке (распознавания), при которой образ Задачи 3-ВЫП попадает в область множества задач о рюкзаках с плотностью d < C, где С – любое положительное вещественное число, не превосходящее 3(log2 7)1.

Научная новизна Основные результаты, полученные в работе, являются новыми. Предложенный метод решения индивидуальных представителей NP-полных Задач – LLL-решатель – является новым и достаточно перспективным для включения в перечень существующих в настоящее время средств решения индивидуальных представителей NP-полных Задач за приемлемое время. Перспективны также новые предложенные методы решения вычислительной Обобщенной Задачи о рюкзаке и систем задач о рюкзаках.

Теоретическая и практическая ценность Работа носит теоретический характер. Методы, применяемые в этой работе, могут быть использованы при проведении исследований инъективных и сверхрастущих векторов, сложности алгоритмов, методов решения индивидуальных представителей NP-полных Задач.

Практические результаты диссертации также могут найти применение в областях, связанных с решением индивидуальных представителей NP-полных Задач, при разработке и исследовании свойств аппаратнопрограммных средств защиты информации.

Материал диссертации представляет интерес для специалистов в области дискретной математики, теории сложности алгоритмов и защиты информации. Работа может быть востребована в российских и международных научных центрах, где ведутся исследования, связанные с изучением алгоритмов и их сложности.

Апробация результатов Основные результаты работы докладывались на научном семинаре, проводимом научно-образовательным центром Ярославского государственного университета им. П.Г. Демидова Нелинейная динамика, а также на семинарах кафедры компьютерной безопасности и математических методов обработки информации Ярославского государственного университета им.

П.Г. Демидова в 2010-2012 годах, и обсуждались на научных конференциях и выставках научно-технического творчества:

1) Одиннадцатый Всероссийский конкурс-конференция студентов и аспирантов Информационная безопасность SIBINFO-2011, г. Томск, апрель 2011 года;

2) Региональный этап Всероссийской выставки молодых исследователей, изобретателей, рационализаторов Шаг в будущее, г. Ярославль, ноябрь 2011 года;

3) XII Всероссийская выставка научно-технического творчества молодежи НТТМ-2012, г. Москва, июнь 2012 года;

4) Международная научная конференция, посвященная 35-летию математического факультета и 25-летию факультета информатики и вычислительной техники Ярославского государственного университета им. П.Г. Демидова, г. Ярославль, март 2012 года;

5) Международная молодежная конференция-школа Современные проблемы прикладной математики и информатики, г. Дубна, 22-27 августа 2012 года;

6) 11 Всероссийская конференция Сибирская научная школа-семинар с международным участием Компьютерная безопасность и криптография – SIBECRYPT’12, г. Иркутск, 3-7 сентября 2012 года;

7) Межрегиональная выставка работ молодых исследователей Шаг в будущее, г. Ярославль, 1-2 ноября 2012 года.

Исследования по теме диссертационной работы были отмечены дипломом победителя конкурса научно-исследовательских работ студентов вузов Ярославской области 2010 года в области естественных наук, г. Ярославль, 2011 год; дипломом первой степени за первое место в Одиннадцатом Всероссийском конкурсе-конференции студентов и аспирантов Информационная безопасность SIBINFO-2011, г. Томск, 2011 год; дипломом за победу во II Внутривузовском конкурсе лучших поисковых научно-исследовательских работ аспирантов Подготовка научно-педагогических кадров в научнообразовательных центрах ВУЗа 2011 года по направлению Информатика, г. Ярославль, 2011 год; дипломом первой степени победителю Регионального этапа Всероссийской выставки молодых исследователей, изобретателей, рационализаторов Шаг в будущее, г. Ярославль, 2011 год; дипломом лауреата премии по поддержке талантливой молодежи, установленной Указом Президента Российской Федерации от 6 апреля 2006 года № О мерах государственной поддержки талантливой молодежи ; медалью и дипломом первой степени победителя Межрегиональной выставки работ молодых исследователей Шаг в будущее 1–2 ноября 2012 года.

Результаты исследований внедрены и используются в рамках учебного процесса в Ярославском государственном университете им. П.Г. Демидова.

Публикации Результаты диссертации опубликованы в 9 работах [1–9], из них 5 статей опубликованы в научных журналах, которые включены в перечень российских рецензируемых научных журналов и изданий для опубликования основных научных результатов диссертаций [1–5], 2 статьи в научных журналах [6, 7] и 2 работы в трудах международных конференций [8, 9].

Структура диссертации Диссертация состоит из введения, трех глав, заключения, списка использованной литературы и приложения. Диссертация содержит 19 рисунков, таблиц. Общий объем диссертации составляет 116 страниц.

Соответствие паспорту специальности Тема и содержание диссертационного исследования соответствует требованиям паспорта специальности 05.13.19 Методы и системы защиты информации, информационная безопасность и соответствует следующим областям исследований паспорта специальности: 1. Теория и методология обеспечения информационной безопасности и защиты информации; 13. Принципы и решения (технические, математические, организационные и др.) по созданию новых и совершенствованию существующих средств защиты информации и обеспечения информационной безопасности.

Личный вклад автора Все результаты, выносимые на защиту, получены автором лично.

Благодарности Автор выражает благодарность своему научному руководителю доктору физико-математических наук, профессору Валерию Георгиевичу Дурневу за постановку задач и постоянное внимание к работе, а также Александру Васильевичу Черемушкину за внимание к работе и ценные замечания.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении к диссертационной работе обоснованы важность и актуальность темы диссертационного исследования, сформулированы цели исследования и решаемые задачи, определены научная новизна, теоретическая и практическая ценность работы.

В первой главе изучаются свойства множеств инъективных и сверхрастущих векторов с натуральными элементами, а также особенности операции сильного модульного умножения.

В главе дается подробное описание проведенных автором компьютерных экспериментов по подсчету инъективных и сверхрастущих векторов;

доказан ряд утверждений, позволяющих сократить трудоемкость подсчета;

представлены результаты соответствующих компьютерных экспериментов.

В теоремах 1 и 3 автором устанавливаются верхние и нижние границы для числа возрастающих инъективных и сверхрастущих векторов с заданными размерностью и максимальным элементом. Обозначим через Vgin(r, M) множество возрастающих инъективных векторов размерности r с максимальным элементом, равным M; Vf g (r, M) – множество сверхрастущих векторов размерности r с максимальным элементом, равным M. Введем в рассмотрение функции F1 (r, M) и F2(r, M) с областью определения N2 такие, что Справедливы следующие теоремы.

Теорема 1. При фиксированном r N и любом натуральном M (за исключением случая r = 1, M = 1, при котором F1 (r, M) = 1) выполняется неравенство где через Cn обозначено число сочетаний.

Теорема 3. При фиксированном r 2 и любом натуральном M выполняется неравенство F2 (r, M) P (M), где P (M) – некоторый полином (r 1)-ой степени от M.

В частности, при фиксированном r 2 и любом натуральном M (при M < 2r1 F2 (r, M) = 0) выполняется неравенство В четвертом разделе первой главы предлагается алгоритм перечисления всех сверхрастущих векторов с фиксированным максимальным элементом в лексикографическом порядке. Алгоритм базируется на следующих основных положениях.

Нетрудно понять, что вектор (1, 2, 22,..., 2r1) является единственным сверхрастущим вектором размерности r с максимальным элементом, не превосходящим 2r1. В работе доказана следующая теорема.

Теорема 2. Все сверхрастущие векторы размерности r могут быть получены из вектора (1, 2, 22,..., 2r1) путем применения к нему некоторого набора из следующих операций:

Pk : (a1,..., ar ) (a1, a2,..., ak + 1, ak+1 + 1,..., ar1 + 2rk2, ar + 2rk1), Эта особенность сверхрастущих векторов позволяет предложить алгоритм, работающий по принципу счетчика, с последовательным применением операций Prr, Pr1,..., P1. Алгоритм позволяет непосредственно строить по сверхрастущему вектору с фиксированным максимальным элементом вектор, следующий за ним в лексикографическом порядке. Справедливо следующее утверждение, дающее представление о сложности предложенного алгоритма.

Утверждение 8. Число итераций предложенного алгоритма перечисления всех сверхрастущих векторов размерности r + 1 с фиксированным максимальным элементом M растет при фиксированном r с ростом M как полином r-ой степени от M.

Обозначим через Vf g (r, < M) множество сверхрастущих векторов размерности r, максимальный элемент которых строго меньше M. Пусть вектор (a1,..., ar ) Vf g (r, < M), тогда операция сильного модульного умножения что (t, m) = 1, с последующим применением процедуры сортировки элементов полученного вектора по возрастанию преобразует вектор (a1,..., ar ) в вектор из множества Vgin(r, < M) возрастающих инъективных векторов размерности r, максимальный элемент которых строго меньше M. Введем обозначение SSMUr,M для этого отображения:

В пятом разделе первой главы диссертационного исследования экспериментально изучаются вопросы о плотности покрытия множества Vgin(r, < M) элементами образа SSMUr,M (Vf g (r, < M)) и равномерности этого покрытия. Дано описание соответствующих компьютерных экспериментов.

Определение 5. Для вектора B размерности r число троек (A = (a1,..., ar ), m, t) (сверхрастущий вектор, модуль, множитель) таких, SORT ((ta1, mod m), (ta2, mod m),..., (tar, mod m)), где SORT – процедура сортировки элементов вектора по возрастанию, назовем числом представлений вектора B.

Введем в рассмотрение функцию плотности F (r, M) с областью определения N2 – ее значения суть отношение числа векторов из Vgin (r, < M), число представлений которых больше нуля, к общему числу элементов множества Vgin(r, < M). Проведенные вычислительные эксперименты позволяют выдвинуть следующую гипотезу.

Гипотеза 1. При фиксированном r N F (r, M) достигает 0,9 при значениях M, близких к 22r2.

Под достижением в гипотезе 1 понимается, что существует такое M N, близкое к 22r2, что F (r, M1) 0,9, но при этом могут существовать такие M > M1, что F (r, M) < 0,9.

В результате компьютерных экспериментов автором установлено, что покрытие множества Vgin (r, < M) элементами образа SSMUr,M (Vf g (r, < M)) не является равномерным.

В шестом разделе первой главы изучается вопрос о монотонности функции F1(r, M) по M. В результате компьютерных экспериментов показано, что при фиксированном 5 r 8 функция F1(r, M) не является монотонной по M. Анализ возможных причин немонотонности функции F1(r, M) позволяет выдвинуть следующие гипотезы.

Гипотеза 2. При фиксированном r {2, 3, 4} функция F1(r, M) является монотонно возрастающей по M.

Гипотеза 3. При фиксированном r 5 функция F1 (r, M) не является монотонной по M.

Кроме того, в шестом разделе первой главы введено понятие инъективного r-представления числа M – такого представления числа M в виr де суммы M = i=1 ai, что вектор (a1,..., ar1 ) является возрастающим инъективным вектором. Показано, что вопрос о монотонности функции F1(r, M) тесно связан с вопросом о том, сколько существует различных rпредставлений числа M.

Во второй главе диссертационной работы разработаны методы решения Обобщенной Задачи о рюкзаке и систем обобщенных и классических задач о рюкзаках, основанные на методе Лагариаса-Одлыжко решения классической вычислительной Задачи о рюкзаке.

В главе рассмотрены LLL-приведенные базисы решетки (дано описание работы алгоритма построения LLL-приведенного базиса решетки, используемого автором при разработке программного обеспечения), а также вопрос о числе точек целочисленной решетки, попадающих в сферу малого радиуса в r-мерном пространстве. Эти вопросы лежат в основе метода ЛагариасаОдлыжко решения вычислительной Задачи о рюкзаке и базируются на работах А. Ленстра, Х. Ленстра и Л. Ловаса11, Х. Кохэна12, Дж. Лагариаса и А. Одлыжко13.

В четвертом разделе второй главы изложен метод ShortVector, предложенный Дж. Лагариасом и А. Одлыжко в работе для решения вычислительной Задачи о рюкзаке, и описан алгоритм Оракул, выдающий за полиномиальное время один из кратчайших ненулевых векторов решеток специализированных описанных в диссертационной работе видов, идея которого была предложена в работе М. Костера и других14.

Напомним формулировку вычислительной Обобщенной Задачи о рюкзаке.

Условие: Заданы вектор A = (a1, a2,..., ar ) Nr, число S N и натуральное число m 2, причем известно, что уравнение где x1,..., xr – неизвестные, имеет решение в числах 0, 1,..., m 1.

Вопрос: Найти решение уравнения (1) в числах 0, 1,..., m 1.

Lenstra A.K., Lenstra H.W., Lovasz L. Factoring Polynomials with Rational Coecients // Mathematische Annalen 261. 1982. p. 515–534.

Cohen H.A. A course in computational algebraic number theory. Springer-Verlag, 1993. 545 p.

Odlyzko A.M., Lagarias J.C. Solving Low-Density Subset Sum Problems. p. 229–246.

Coster M.J., Joux A., LaMacchia B.A., Odlyzko A.M., Schnorr C.-P., Stern J. Improved low-density subset sum algorithms. p. 111–128.

В пятом разделе второй главы диссертации предложен метод решения вычислительной Обобщенной Задачи о рюкзаке, основанный на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке. Показано, что предложенный метод решает практически все вычислительные Обобщенные Задачи о рюкзаке, обладающие плотноr ln m стью dОЗР = log (max1 i r ai) < (m1) Рассмотрим решетку 3, образованную следующими векторами b1,..., br+1 размерности r+1: b1 := (1, 0,..., 0, N ·a1), b2 := (0, 1,..., 0, N ·a2), N (m 1) 2 + 1 – некоторое достаточно большое натуральное число.

Для любого натурального числа m 2 справедлива следующая теорема.

Теорема 11. Пусть a1,..., ar – произвольные натуральные числа, e = (e1,..., er ) {0, 1,..., m 1}r – произвольный вектор и S = r ei ai.

Тогда вероятность ошибки при решении приведенной обобщенной задачи о рюкзаке, заданной значениями ai, 1 i r, и S, при условии, что плотln m примененного к решетке 3, стремится к 0 при r.

Напомним формулировку системы обобщенных задач о рюкзаках, метод решения которой предложен в шестом разделе второй главы.

Условие: Заданы k векторов A1 = (a11,..., ar1 ),..., Ak = (a1k,..., ark ) S1,..., Sk и натуральное число m 2, причем известно, что система уравнений где x1,..., xr – неизвестные, имеет решение в числах 0, 1,..., m 1.

Вопрос: Найти решение системы уравнений (2) в числах 0, 1,..., m 1.

Предложенный метод решает практически все системы обобщенных задач о рюкзаках, обладающие плотностью dСОЗР = Обобщенная задача о рюкзаке является приведенной, если выполнены неравенства ai Рассмотрим решетку 4, образованную следующими векторами b1,..., br+1 размерности r + k: b1 := (1, 0,..., 0, N · a11, N · a12,..., N · a1k ), N [(m 1) 2 ] + 1 – некоторое достаточно большое натуральное число.

Для любого натурального числа m 2 справедлива следующая теорема.

Теорема 12. Пусть aij, 1 i r, 1 j k, – произвольные натуральные числа, причем векторы A1 = (a11,..., ar1 ),..., Ak = (a1k,..., ark ) являются линейно независимыми. Пусть e = (e1,..., er ) {0, 1,..., m 1}r ятность ошибки при решении приведенной системы обобщенных задач о рюкзаках, заданной значениями aij, 1 i r, 1 j k, и Sj, 1 j k, мощью алгоритма Оракул, примененного к решетке 4, стремится к при r.

В седьмом разделе второй главы рассмотрен особый случай (m = 2) системы обобщенных задач о рюкзаках – система задач о рюкзаках.

С точки зрения информационной безопасности, система задач о рюкзаках тесно связана со случаем широковещательной рассылки сообщения, например, в системе Меркля-Хеллмана. Предложенный в этом разделе метод решения системы задач о рюкзаках позволяет решать практически все системы, обладающие плотностью dСЗР = log (max1 ir r,1 j k aij ) < k · 0,9408...

Рассмотрим решетку 5, образованную следующими векторами b1,..., br+1 размерности r + k: b1 := (1, 0,..., 0, N · a11, N · a12,..., N · a1k ), N [ 2 r] + 1 – некоторое достаточно большое натуральное число.

Справедлива следующая теорема.

ральные числа, причем векторы A1 = (a11,..., ar1 ),..., Ak = (a1k,..., ark ) являются линейно независимыми. Пусть e = (e1,..., er ) {0, 1}r – произr вольный вектор и Sj = i=1 ei aij для всех 1 j k. Тогда вероятность ошибки при решении системы задач о рюкзаках, заданной значениями aij, 1 i r, 1 j k, и Sj, 1 j k, при условии, что плотность этой сиСистема обобщенных задач о рюкзаках является приведенной, если для всех 1 j k выполнены неравенства 1 i=1 aij Sj (m 1) i=1 aij 1 i=1 aij.

стемы dСЗР < k · 0,9408..., с помощью алгоритма Оракул, примененного к решетке 5, стремится к 0 при r.

В третьей главе диссертационного исследования установлена связь между инъективными векторами заданной размерности r, обладающими наименьшим максимальным элементом (эти векторы обладают наибольшей плотностью среди всех инъективных векторов заданной размерности) и последовательностью Штерна b1 = 1, b2 = 1, b3 = 2, b4 = 3, b5 = 6, b6 = 11, b7 = 20, b8 = 40...

В следствии 7 и утверждении 11 получены верхние и нижние оценки для значений элементов последовательности Штерна {bi}, i N, а именно для любого натурального l 3 выполнены неравенства Кроме того, в предположении, что один из инъективных векторов (a1,..., ar ) размерности r 2, обладающий наименьшим максимальным элементом среди всех инъективных векторов размерности r, может быть построен по правилу где b1,..., br – суть первые r элементов последовательности Штерна b1 = 1, b2 = 1, b3 = 2, b4 = 3, b5 = 6, b6 = 11, b7 = 20, b8 = 40..., установлена верхняя граница для плотности инъективных векторов. При оговоренных условиях является справедливой следующая теорема.

Теорема 14. Плотность din инъективных векторов размерности r 4 удовлетворяет неравенству Во втором разделе третьей главы рассматриваются вопросы о том, в какую область множества задач о рюкзаках (относительно плотности) попадают при полиномиальной трансформации образы NP-полных Задач распознавания 3-ВЫП, Раскрашиваемость, Точное покрытие, и какая доля задач из образа попадает в область множества задач о рюкзаках с плотностью меньше, чем 0,9408...

Рассмотрена полиномиальная трансформация T1 Задачи о точном покрытии в Задачу о рюкзаке, впервые описанная Р. Карпом15, для которой доказано следующее утверждение (p и l – параметры Задачи о точном покрытии).

Утверждение 13. При полиномиальной трансформации T1 Задачи о точном покрытии в Задачу о рюкзаке образ задач о точном покрытии, удовлетворяющих условию лежит в области множества задач о рюкзаках, при решении которых с помощью алгоритма Оракул вероятность получения неверного ответа стремится к нулю при условии, что размерность задачи стремится к бесконечности.

Показано, что задачи о точном покрытии, удовлетворяющие условию 0,9408..., составляют значительную долю задач о точном поp1) log2 (l+1) крытии. Доказано следующее утверждение.

Утверждение 14. Число задач о точном покрытии, удовлетворяющих условию асимптотически мало по сравнению с числом задач о точном покрытии, удовлетворяющих условию Рассмотрены полиномиальная трансформация T2 Задачи о раскрашиваемости в Задачу о точном покрытии, описанная в монографии А. Ахо, Дж. Хопкрофта и Дж. Ульмана16, и конкатенация полиномиальных трансформаций T1 и T2 (обозначенная через T1 T2 ). Доказано следующее утверждение (|V |, |E| и k – параметры Задачи о раскрашиваемости).

Утверждение 19. При полиномиальной трансформации T1 T2 Задачи о раскрашиваемости в Задачу о рюкзаке образ задач о раскрашиKarp R.M. Reducibility among combinatorial problems // Complexity of Computer Computations: Proc.

of a Symp. on the Complexity of Computer Computations, The IBM Research Symposia Series. 1972. p. 85– 103.

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. С. 439–440.

ваемости, удовлетворяющих условию лежит в области множества задач о рюкзаках, при решении которых с помощью алгоритма Оракул вероятность получения неверного ответа стремится к нулю при условии, что размерность задачи стремится к бесконечности.

Рассмотрены полиномиальная трансформация T3 Задачи 3-ВЫП в Задачу о раскрашиваемости, описанная в монографии А. Ахо, Дж. Хопкрофта и Дж. Ульмана17, и конкатенация полиномиальных трансформаций T1 T2 T3. Доказано следующее утверждение (n и t – параметры Задачи 3-ВЫП).

Утверждение 21. При полиномиальной трансформации T1 T2 T3 Задачи 3-ВЫП в Задачу о рюкзаке образ задач 3-ВЫП, удовлетворяющих условию лежит в области множества задач о рюкзаках, при решении которых с помощью алгоритма Оракул вероятность получения неверного ответа стремится к нулю при условии, что размерность задачи стремится к бесконечности.

Кроме того, показано, что справедливо следующее утверждение.

Утверждение 22. Множество задач о рюкзаках, обладающих плотностью меньшей, чем 0,9408..., является NP-полной Задачей.

Рассмотрена полиномиальная трансформация T4 Задачи 3-ВЫП в Задачу о рюкзаке, описанная в монографии Т. Кормена, Ч. Лейзерсона, Р. Ривеста и К. Штайна18. Эта трансформация обладает тем свойством, что размерность r задач о рюкзаках, получаемых с ее помощью, линейно зависит от параметров Задачи 3-ВЫП, поэтому трансформация T4 гораздо более приемлема при практической реализации, чем трансформация T1 T2 T3, у которой эта зависимость полиномиальная. Доказана следующая теорема.

Теорема 15. При полиномиальной трансформации T4 Задачи 3-ВЫП в Задачу о рюкзаке образ Задачи 3-ВЫП попадает в область множеАхо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. С. 437–438.

Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2005.

С. 1140–1144.

ства задач о рюкзаках с плотностью d < C6, где С – любое положительное вещественное число, не превосходящее 3(log2 7)1.

Теорема 15 утверждает, что каким бы положительным вещественным числом, не превосходящим log 7, ни была ограничена плотность задач о рюкзаках, можно вложить образ Задачи 3-ВЫП в область множества задач о рюкзаках, обладающих этой плотностью. Из чего можно заключить, что любое множество задач о рюкзаках, обладающих плотностью d log 7, является NP-полной Задачей.

В третьем разделе третьей главы предлагается подход к решению за приемлемое время представителей NP-полных Задач – LLL-решатель, основанный на методе решения вычислительной Задачи о рюкзаке, предложенном Дж. Лагариасом и А. Одлыжко.

Для анализа результативности предлагаемого подхода вводится понятие функции применимости алгоритма (метода).

Рассматриваются функции применимости LLL-решателя к приведенным задачам о рюкзаках при фиксированном r и max1 i r ai. Экспериментально полученные значения этих функций (при r < 9) говорят о высокой степени результативности LLL-решателя. В результате вычислительных экспериментов, в ходе которых решались более 20 миллиардов различных задач о рюкзаках малых размерностей (r < 9), автором установлено, что характер смещения ветвей функций применимости LLL-решателя с ростом r в случае, если в качестве претендента на вектор, дающий решение задачи о рюкзаке, рассматривается только первый вектор LLL-приведенного базиса, не является равномерным. Этот экспериментальный результат выглядит сильнее по сравнению с прогнозом, основанным на теории Лагариаса-Одлыжко, предполагающим равномерное падение применимости LLL-решателя.

В Выводах к каждой главе даны общие выводы из проделанной работы.

В Заключении к диссертационной работе обозначены направления дальнейших исследований и указаны нерешенные проблемы. В частности указаны: возможность развития метода получения верхней оценки для числа сверхрастущих и инъективных векторов, элементы которых являются натуральными числами, с заданными размерностью и максимальным элементом и три возможных направления развития LLL-решателя (совершенствование алгоритма, поиск новых видов решеток, управление параметрами получаемого при трансформации образа Задачи).

Список публикаций по теме диссертации Статьи в научных журналах, которые включены в перечень российских рецензируемых научных журналов и изданий для опубликования основных научных результатов диссертаций 1. Мурин, Д.М. О порядке роста числа инъективных и сверхрастущих рюкзачных векторов / Д.М. Мурин // Моделирование и анализ информационных систем.

2012. Т. 19, № 3. С. 124–135. – 1,33 п. л.

2. Мурин, Д.М. О некоторых свойствах образов трансформированных Задач / Д.М. Мурин // Прикладная дискретная математика. 2012. № 3(17). С. 96– 3. Мурин, Д.М. LLL-решатель / Д.М. Мурин // Математическое моделирование.

2012. Т. 24, № 12. С. 43–48. – 0,64 п. л.

4. Мурин, Д.М. О верхней границе плотности инъективных векторов / Д.М. Мурин // Прикладная дискретная математика. 2013. № 1(19). С. 117–124. – 5. Мурин, Д.М. Модификация метода Лагариаса-Одлыжко для решения обобщенной задачи о рюкзаке и систем задач о рюкзаках / Д.М. Мурин // Прикладная дискретная математика. 2013. № 2(20). С. 91–100. – 1,16 п. л.

Публикации в других научных изданиях 6. Мурин, Д.М. О порядке роста числа инъективных и сверхрастущих векторов и некоторых особенностях сильного модульного умножения / Д.М. Мурин // Прикладная дискретная математика. Приложение. 2012. № 5. С. 19–21. – 0, 7. Мурин, Д.М. О некоторых свойствах инъективных векторов / Д.М. Мурин // Современные проблемы математики и информатики: сборник научных трудов молодых ученых, аспирантов и студентов. Ярославль, ЯрГУ. 2013. Вып. 13.

8. Мурин, Д.М. О некоторых свойствах отображения множества сверхрастущих векторов во множество инъективных векторов с помощью сильного модульного умножения / Д.М. Мурин // Моделирование и анализ информационных систем. Труды международной научной конференции, посвященной 35-летию математического факультета и 25-летию факультета информатики и вычислительной техники Ярославского государственного университета им. П.Г. Демидова. Ярославль, ЯрГУ.

2012. С. 137–139. – 0,35 п. л.

9. Мурин, Д.М. LLL-решатель / Д.М. Мурин // Международная молодежная конференция-школа Современные проблемы прикладной математики и информатики, 22-27 августа 2012 г. Дубна. ОИЯИ. 2012. С. 155–158. – 0,4 п. л.