автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Информационная технология минимизации функционалов, ассоциированных с задачей выполнимость

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

ХНЫКИН Иван Геннадьевич

ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ МИНИМИЗАЦИИ ФУНКЦИОНАЛОВ, АССОЦИИРОВАННЫХ С ЗАДАЧЕЙ ВЫПОЛНИМОСТЬ

Специальность 05.13.17 - Теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Омск - 2009

1 о ДЕК 2009

003487509

Работа выполнена в государственном образовательном учреждении высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского» на кафедре безопасности информационных систем.

Научный руководитель доктор технических наук, профессор

Файзуллин Рашит Тагирович

Официальные оппоненты: доктор физико-математических наук

Чернов Владимир Михайлович

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

Цветов Виктор Петрович

Ведущая организация: Институт математики и механики

Уральского отделения Российской академии наук

Защита состоится 23 декабря 2009 г. в 12 часов на заседании диссертационного совета Д 212.215.07, созданном при государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева», по адресу: 443086, г. Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке Государственного образовательного учреждения высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева».

Автореферат разослан 20 ноября 2009 г.

Ученый секретарь диссертационного совета

доктор технических наук, профессор

Белоконов И.В.

Общая характеристика работы

Целью диссертационной работы является разработка информационной технологии решения задачи ВЫПОЛНИМОСТЬ посредством итерационных алгоритмов минимизации функционалов, ассоциированных с непрерывной моделью исследуемой дискретной задачи.

Актуальность работы. Задача ВЫПОЛНИМОСТЬ — одна из наиболее важных задач информатики в целом. На практике к решению задачи ВЫПОЛНИМОСТЬ сводятся многие проблемы, возникающие при синтезе систем искусственного интеллекта, при проектировании компьютерных систем, в задачах роботостроения, криптографии и других. Сведению задач из различных областей прикладной математики к задаче ВЫПОЛНИМОСТЬ посвящены работы Ю.И.Журавлева, А.А.Семенова Е.В.Буранова, Ю.Г.Сметанина, А.А.Ушакова, F. Massacci, L.Marraro и других. Одна из причин этого - потенциальная возможность решать задачи, возникающие в самых различных областях, единым алгоритмом решения задачи ВЫПОЛНИМОСТЬ. Следует отметить, что к решению указанной задачи сводятся многие проблемы дискретной математики, для которых доказано отсутствие алгоритмов полиномиальной сложности, то есть, их «труднорешаемость».

Однако, доказанный факт этой труднорешаемости, справедливый для всего (бесконечного) множества параметров, характеризующих ту или иную конкретную задачу, доказанный часто построением единственного экстремального примера, не снимает как саму проблему построения эффективных алгоритмов решения задачи в ограниченном, «пользовательском» диапазоне параметров, так и безусловную практическую значимость проблемы синтеза таких эффективных алгоритмов. В частности, возможность сведения задач факторизации больших целых чисел, дискретного логарифмирования, дискретного логарифмирования на эллиптической кривой к задаче ВЫПОЛНИМОСТЬ делает разработку моделей и алгоритмов её решения особенно актуальной, так как перечисленные задачи являются теоретической основой для разработки систем криптографической обработки данных, повышения надежности современных систем телекоммуникаций, систем финансовых взаиморасчетов и других.

Как показал опыт, применение переборных алгоритмов решения задачи ВЫПОЛНИМОСТЬ сталкивается с принципиальными трудностями: задачи больших размерностей оказываются недоступными для переборных алгоритмов. Естественно, возникает идея перехода к непрерывным моделям, когда поиск выполняющего набора для соответствующей конъюнктивной нормальной формы (КНФ) осуществляется как поиск экстремума, ассоциированного с КНФ непрерывного функционала. Впервые эта идея была реализована в работах С.Ю. Маслова, В.Я. Крейновича и получила дальнейшее развитие в работах R. Sosie, J. Gu, A. Torn, A. Zilinskas. Следует отметить, что, имеется принципиальное отличие непрерывных методов от переборных алгоритмов

з

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

Тем не менее, известные автору непрерывные методы не удовлетворяют современным потребностям, возникающим при решении задач ВЫПОЛНИМОСТЬ. Одни из них достаточно эффективно находят решение только для задач небольших размерностей, другие показывают хорошие результаты только на задачах для КНФ специальной структуры. Наконец, указанные методы показывают низкую эффективность при решении задач ВЫПОЛНИМОСТЬ, ассоциированных с задачами факторизации больших целых чисел, дискретного логарифмирования, дискретного логарифмирования на эллиптической кривой.

В диссертационном исследовании за основу взят непрерывный метод минимизации функционалов, т.н. метод последовательных приближений с «инерцией», описанный в работах Р.Т. Файзуллина. В оригинальном виде указанный метод оказывается недостаточно эффективным в применении к функционалам, полученным при различных способах моделирования КНФ. Предлагается улучшить характеристики метода последовательных приближений с «инерцией» путем его интеграции с оригинальными и известными подходами, способствующими увеличению эффективности.

Для последовательной реализации указанной идеи необходимо разработать оригинальные и адаптировать известные подходы (как непрерывные, так и дискретные), используемые в методах решения задачи ВЫПОЛНИМОСТЬ. При этом следует максимально обобщить данные подходы для возможности их применения не только в методе последовательных приближений с «инерцией». Кроме того, эффективность данных подходов должна проявляться в применении к КНФ с различной структурой. Хотя предпочтение все же отдается задачам ВЫПОЛНИМОСТЬ, ассоциированным с задачами факторизации больших целых чисел, дискретного логарифмирования, дискретного логарифмирования на эллиптической кривой. Вышеуказанные положения определяют структуру диссертационной работы и содержание отдельных глав.

Научная новизна работы. В диссертационной работе получены следующие научные результаты:

Разработана стратегия применения правил резолюции для преобразования КНФ и исследована ее эффективность.

Разработаны и обоснованы подходы, улучшающие сходимость градиентных методов поиска решения задачи ВЫПОЛНИМОСТЬ для КНФ различной структуры.

Разработан способ построения множества булевых векторов (битовой записи чисел), в среднем на 68% совпадающих с решением задачи факторизации целых чисел больших размерностей (до 3072 бит включительно).

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

На защиту выносятся следующие результаты:

Стратегия применения правил резолюции для преобразования КНФ различной структуры как препроцессор для методов поиска решения задачи ВЫПОЛНИМОСТЬ.

Подходы, улучшающие сходимость градиентных методов поиска решения задачи ВЫПОЛНИМОСТЬ для КНФ различной структуры.

Гибридный метод последовательных приближений с «инерцией» как способ нахождения областей, близких к решению задачи факторизации больших целых чисел.

Апробация работы. Результаты работы опубликованы, в том числе и в рецензируемых журналах и прошли апробацию на научных конференциях и семинарах: Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Красноярск, 2006), 10-й Московской международной телекоммуникационной конференции студентов и молодых ученых (2007), Региональной молодежной конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, 2007), Межрегиональной конференции Современные математические методы и информационные технологии (Тюмень, 2007), «Параллельные вычислительные технологии» (Нижний Новгород, 2009).

Публикации. Основные результаты диссертации опубликованы в 10 работах, из них 4 в рецензируемых изданиях и журналах, рекомендованных ВАК.

Личный вклад. Автором разработаны оригинальные и адаптированы известные подходы, увеличивающие эффективность градиентных методов, в том числе стратегия применения правил резолюции, сдвиг по антиградиенту, метод смены траектории и др. Исследована их эффективность. Предложена система дополнительных тестов, позволяющая с высокой долей вероятности определять конкретные биты сомножителей в задаче факторизации целых чисел размерности 512 бит. Указанные подходы интегрированы с методом последовательных приближений с «инерцией» и исследована эффективность полученного гибридного метода в применении к поиску решения задач ВЫПОЛНИМОСТЬ для КНФ различной структуры, в особенности для КНФ, ассоциированных с задачами факторизации больших целых чисел, дискретного логарифмирования, дискретного логарифмирования на эллиптической кривой. Гибридный метод адаптирован для поиска областей (множества двоичных чисел), близких к решению задач факторизации больших размерностей (до 3072 бит включительно).

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

Структура диссертации. Диссертационная работа состоит из введения, трех глав, заключения, библиографии.

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

В первой главе представлены необходимые сведения из булевой алгебры, приводится постановка задачи. Описаны различные математические модели задачи ВЫПОЛНИМОСТЬ. Рассматриваются наиболее популярные алгоритмы и общие схемы методов поиска решающего набора задачи ВЫПОЛНИМОСТЬ для КНФ. Основное внимание уделяется вопросу сведения задачи ВЫПОЛНИМОСТЬ к задаче непрерывной минимизации и применения градиентных методов поиска точек экстремума. Глава не содержит новых результатов и включена в работу для замкнутости изложения и удобства ссылок.

Задача ВЫПОЛНИМОСТЬ заключается в том, чтобы определить, выполнима ли данная формула в КНФ и найти набор(ы) значений булевых переменных, при которых пропозициональная формула выполнима.

Пусть дана КНФ, на множестве булевых переменных у = {у1,...уы}еВ»{ 0,1}: и

L(y) = л G,(y), где i=i

G,-дизъюнкты вида v Лу)

{у j, если у j входит в G,

у j, если у j входит в G, (1)

N - число переменных, М - число дизъюнктов В работах Колоколова A.A., Адельшина A.B., Ягофаровой Д.И. предлагается использовать модель линейного целочисленного программирования (ЦЛП) для возможности применения методов оптимизации при поиске решения задачи ВЫПОЛНИМОСТЬ:

min F(x) = min Х\ xeRN[0,\] xeRN[ ОД]

g! G-Xi e Z[0, 1]

Здесь р,- - число литералов, входящих в й дизъюнкт с отрицанием.

В работах Крейновича В.Я. предложен ряд непрерывных моделей, сводящих задачу ВЫПОЛНИМОСТЬ к задаче безусловной глобальной минимизации функционала, например:

min F(x)= min Т(Цу))

«ЙЛ[0,1] iE Л "[0,1]

1. Г(0) = 0 2. Г(1) = оо

Цу,) = х, Т(у,) = Мх,

Т(у, V уj) = шах(х,, X J), Т(у, А у J) = (1 / х, +1 / Xj )"';

Ух £-ß{0,l}, Jr, sä[0,oo), i = \...N

Здесь и далее по тексту Т(у) - литерная функция, определяющая соответствие между булевым пространством и множеством, в котором предполагается осуществлять поиск решения.

В работах Опарина Г.А., Новопашина А.П. предлагается еще ряд вариантов сведения задачи ВЫПОЛНИМОСТЬ к поиску точек глобальных минимумов специальным образом построенного функционала, например: min F(x)= min T(L{y))

16 R" [0,1] *еЛ"[0,1]

1. 7(0) = 0 2. 7X1) = 1

T(yi) = xt T{yt) = 1-х,

T(y, v yj) = xi +Xj, Т(у, л yj) = minix^x;).

y,eß{0,l}, x(eÄlO,oo), i = L..N

В обзоре J.Gu представлены как дискретные, так и непрерывные модели задачи ВЫПОЛНИМОСТЬ. В данной диссертационной работе используется непрерывная формулировка задачи ВЫПОЛНИМОСТЬ для ДНФ:

м

min F(x) = min £с,(х)

Ф) = \\ри{х) (2)

;=1

Pi j W =

(xj -1)2,если у j входит в G, (Xj)2, если y>j входит в Gt 1, иначе

Преимущества данной модели задачи ВЫПОЛНИМОСТЬ по сравнению с рассмотренными в данной работе моделями в том, что целевая функция (полином) имеет наименьшую возможную (квадратичную) степень по переменным среди дифференцируемых положительно определенных функций в

Я".

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

Одним из самых первых полных (дискретных) переборных алгоритмов следует считать процедуру БР, разработанную в 1960 году американскими математиками М.Эау1з и Н.РиШат. Данный алгоритм основан на классическом методе резолюций математической логики.

В процедуре ОР выбирается одна из переменных и вычисляются все резольвенты по этой переменной. Вычисленные резольвенты конъюнкцией добавляются к исходной КНФ. Все дизъюнкты исходной КНФ, участвовавшие в формировании резольвент, удаляются. При этом полученная формула эквивалентна исходной в том смысле, что она выполнима тогда и только тогда, когда выполнима исходная КНФ. Процесс повторяется для всех переменных. Процедура завершает работу, если все резольвенты вычислены, либо если получен пустой дизъюнкт. В последнем случае исходная КНФ не имеет решения.

Развитием процедуры ОР стал полный алгоритм поиска ОРЬЬ, представленный американскими математиками M.Davis, Н.РиШаш, О.Ьо§етапп, О.Ьоуе1апс1 в 1962 году. Данный алгоритм основан на т.н. методе разделения с возвратом (бэктрекинга). На основе некоторой эвристики выбирается переменная, которой присваивается значение 1. КНФ разрешается относительно данной переменной, затем рекурсивно проверяется выполнимость полученной КНФ. Если формула невыполнима, алгоритм возвращается на шаг назад и выбранной на этом шаге переменной присваивается противоположное значение 0. По сути, на каждом шаге рекурсии КНФ разбивается на две формулы, полученные из данной КНФ путем установки выбранной переменной в значение 1 и 0 соответственно. В итоге получаем дерево формул, корень которого — исходная КНФ, узлы -формулы, получаемые из предыдущих формул путем разрешения по выбранной переменной. Дуги (ветви) могут быть обозначены по именам литералов, относительно которых происходит разрешение. Данное дерево называется деревом поиска решения.

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

Другим подходом в решении задачи ВЫПОЛНИМОСТЬ является метод локального поиска. Примером алгоритма локального поиска является следующий: исходная КНФ представляется в виде целевой функции, представляющей число невыполненных дизъюнктов на данном наборе значений переменных, затем некоторым образом решается задача минимизации целевой функции.

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

Локальный поиск эффективен по двум причинам. Во-первых, метод не перебирает все точки пространства поиска, а фокусируется на одной траектории поиска вектора решения в зависимости от стартового вектора. Во-вторых, каждая итерация состоит из поиска соседнего вектора для улучшения текущего вектора приближений. А так как размерность целевой функции полиномиально зависит от размерности входных данных (КНФ), то итерации происходят относительно быстро.

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

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

Методы глобальной оптимизации направлены на поиск глобального экстремума задачи. При этом подходы, которые рассматриваются в рамках данной группы методов, отличаются поиском в некотором роде оптимальной траектории поиска экстремума. Методы глобальной оптимизации могут использовать подходы, реализованные в методах локального поиска (например, градиентный локальный поиск), а также подходы непрерывной оптимизации и подходы из линейной алгебры. Одним из ярких примеров среди непрерывных методов глобальной оптимизации является классический непрерывный метод Лагранжа.

Во второй главе обосновывается выбор функционала специального вида, ассоциированного с задачей ВЫПОЛНИМОСТЬ. Предлагается применить к решению системы нелинейных алгебраических уравнений, определяющих стационарные точки функционала, модифицированный метод последовательных приближений (с «инерцией»).

Общая схема метода последовательных приближений с «инерцией» в применении к решению задачи ВЫПОЛНИМОСТЬ следующая.

1. Осуществляется переход от задачи ВЫПОЛНИМОСТЬ к эквивалентной задаче поиска экстремума в пространстве Л* [0,1]. Переход основан на

(3)

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

2. Для поиска точки глобального минимума построенного функционала применяется модифицированный метод последовательных приближений.

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

Переход от задачи ВЫПОЛНИМОСТЬ к задаче поиска глобального минимума функционала происходит по формуле (2). При этом справедливо следующее утверждение 1:

Утверждение 1. Задача ВЫПОЛНИМОСТЬ для КНФ имеет решение, тогда и

только тогда, когда <=> 3 х* е R N: min F(x) = F(x*) = 0.

xeRN

Дифференцируя функционал по всем переменным, и приравнивая к О, получаем систему нелинейных уравнений для поиска стационарных точек:

[ I Па,/*,)]'*, - X Пд,Д*;)=о

i = l...N

{E(Xj)} = Е = {множество индексов к: х, или х, входит в Gk}

def def

{Л(х,)} = Л = {множество индексов к: х, входит в Gk}

def def

Для поиска решения системы уравнений (3) предлагается применить модифицированный метод последовательных приближений, так называемый метод последовательных приближений с «инерцией», описанный в работах Файзуллина Р.Т., где он хорошо зарекомендовал себя при решении систем нелинейных уравнений гидравлики:

Vi *=0

л, (0-*,(f+i) = в, (0 (4)

К-1

=1, ак 6 R, ак> О, К> 1

к=о

Отметим, что классический метод Ньютона в применении к решению системы уравнений (3) неустойчив, что подтверждается теоремой 1.

Теорема 1. Решение системы нелинейных уравнений (3) входит в ядро производного оператора.

Далее в работе разрабатываются методики улучшения сходимости метода (4).

Переход к задаче 3-ВЫПОЛНИМОСТЬ. Любая процедура решения системы (3) при произвольной длине дизъюнктов будет естественным образом приводить к большим ошибкам округления. Другая проблема, возникающая при

I YlPi,j(xj('-k))

йл j* def

решении задач ВЫПОЛНИМОСТЬ, заключается в том, что градиентные методы могут не сходиться вообще. Частично это подтверждается теоремой 2.

Теорема 2. Существует класс КНФ, для которого существует траектория, на которой скорость сходимости метода Ньютона становится линейной и бесконечно малой при произвольной длине дизъюнктов и выборе модели представления КНФ (2).

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

Одним из способов преодоления этой технической трудности является представление исходной КНФ в виде эквивалентной 3-КНФ и применение метода поиска решения уже к 3-КНФ.

Однако при переходе к 3-КНФ количество переменных и дизъюнктов увеличивается, что также может негативно сказываться на сходимости методов решения задачи ВЫПОЛНИМОСТЬ. Альтернативным подходом является предварительная обработка исходной КНФ с помощью правил резолюции и уже затем сведение к 3-КНФ.

Стратегия применения правил резолюции. Решение многих практических задач сводится к решению специальным образом сформированных КНФ. Проблема состоит в том, что получаемые КНФ имеют большое количество дизъюнктов и переменных даже при небольшой размерности исходной задачи. С помощью применения правил резолюции можно добиться преобразования исходной КНФ в эквивалентную КНФ, с меньшим количеством дизъюнктов и переменных. Эквивалентность означает, что множества решающих наборов обеих формул одинаковы.

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

Используя правила вывода:

TRUEvx-TRUE

FALSE v х ~ х

xv->х - TRUE

X A —iX ~ □ (пустой дизъюнкт) наряду с вычислением резольвент (метод бинарной резолюции):

(х v Р) л (-ix v Q) -> Р v Q удается значительно сократить размер КНФ (число дизъюнктов), а в отдельных случаях даже получить решение.

Бинарная резолюция сама по себе является полным алгоритмом решения задачи ВЫПОЛНИМОСТЬ, но из-за больших временных затрат не нашла применения в данной области. Поэтому при практическом использовании бинарной резолюции необходимо ограничивать глубину рекурсии. Резольвенты могут вычисляться из дизъюнктов, которые сами являются резольвентами, добавленными на предыдущих шагах метода. Глубина рекурсии устанавливает, до

и

каких пор нужно брать резольвенты от резольвент. Например, глубина рекурсии 1 устанавливает, что можно брать резольвенты только от дизъюнктов исходной КНФ.

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

Добавление весовых множителей (регуляризация). Обобщением метода последовательных приближений с «инерцией» с использованием весовых параметров (4) является добавление весовых множителей в правые части системы нелинейных уравнений (3) и к самим компонентам приближения:

к=О

I ПР,,М'-к))

2>/ I П Ри№-к))

к=0 }*•

Л, (0 ■*,(' + !) = 5,(0

К-1

= 1, ак е Я, ак> 0,

к=0

2>**=1, а*к>0 Д е Л, Д>0, К>1

к=0

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

Таким образом, на каждой итерации происходит неравномерное продвижение по каждой оси многомерного пространства.

Сдвиг по ангиградиенту является поправкой текущего приближения, для улучшения сходимости модифицированного метода последовательных приближений с «инерцией» и производится по формуле:

х(Г + 1) = х(0 + —^5—-г(0, т = А(х(1))-х(1)-В(х(0), ЗеЛ А(х( 0)

Метод смены траектории и туннелирования. Поиск точки глобального минимума градиентными методами может затрудняться из-за наличия точек локальных минимумов функционала (2), так как траектория, образованная

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

Теорема 3. Существует класс КНФ, для которых ассоциированный функционал (2) имеет стационарные точки, отличные от решения соответствующей задачи ВЫПОЛНИМОСТЬ.

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

Рассмотрим множества переменных:

Ек = {х, | сумма Gj(x(t)) = К, причем*, илих, входитв Gt } (5)

к

Введем вероятности Рк > 0: £ Pt■.= 1. С вероятностью рк поменяем каждое

/=1

значение xj (/) е ЕК на противоположное. При этом, вероятность того, что другие слагаемые функционала F(x) (2) примут значение >0, зависит от rk и размерности слагаемых (скобок) из ек и тем ниже, чем меньше К.

Экспериментально установлено, что при К= 0 или £=1 полученный вектор обладает свойствами не худшими, чем исходный вектор приближения. Количество слагаемых, принимающих значение >0 до и после операции примерно одинаково и может быть оценено с помощью теоремы 4.

Теорема 4. Любой дизъюнкт 3-КНФ, сгенерированной псевдослучайным заполнением дизъюнктов (распределение равномерное) из п переменных (и>2) после применения метода смены траектории (К=0) примет значение 0 с вероятностью не выше [3(2л -1)(2п - 2) +18(2« - 2) + 57] /[8и(2п -1)(2п - 2)].

Используя полученный вектор в качестве нового начального приближения, метод приближений быстро (в большинстве случаев за 5-10 итераций) находит следующее приближение, на котором функционал F(x) достигает значения не больше, чем на векторе x(i). При этом, очень часто, удается проскочить область локального минимума. При дальнейшем движении по новой траектории метод может зациклиться в другой области локального минимума. Тогда метод смены траектории повторяется.

Ясно что, чем выше К и больше вероятности rt для «больших» К, тем меньшую роль играет рестарт программы.

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

метода последовательных приближений с «инерцией» — это параметры методов сдвига по антиградиенту, туннелирования, смены траектории и др.

Выбор метода проектирования. Проектирование текущего вещественного вектора приближений на булево пространство и обратный переход от булева вектора к вещественному вектору (с координатами 0 или 1) используется во многих подпрограммах модифицированного метода последовательных приближений. Например, при проверке текущего приближения на решение исходной задачи ВЫПОЛНИМОСТЬ, в методе туннелирования для определения следующего приближения при преодолении локальных минимумов, методе смены траектории для определения следующего приближения при преодолении плато и др. Экспериментально установлено, что следующий метод проектирования является достаточно эффективным: 'х, > 0.5 + => у, = ИСТИНА

■ х, <0.5-е4 => у,; = ЛОЖЬ

jc, е [0.5 - £4,0.5 + £4] => у, = RAND(ИСТИНА, ЛОЖЬ)

И в обратную сторону: у: = ИСТИНА => х, = 1, у, = ЛОЖЬ => = 0 RAND(x, у) - функция, которая равновероятным образом возвращает одно из двух значений х или у.

Увеличение разрядности. Для уменьшения влияния ошибок округления на результат при реализации итерационной процедуры было предусмотрено использование вычислений с произвольной точностью. Исследования сходимости метода при увеличении разрядности вычислений показали преимущество использования типа DOUBLE (двойная точность, 64 бит) по сравнению с типом FLOAT (одинарная точность, 32 бит). При этом дальнейшее увеличение разрядности к значимому эффекту не приводит.

Гибридный метод последовательных приближений с «инерцией» заключается в объединении описанных методик в единый метод, названный гибридным (модифицированным) методом последовательных приближений с «инерцией». Метод аккумулирует наиболее эффективные приемы, используемые в ведущих алгоритмах решения задачи ВЫПОЛНИМОСТЬ, а также новые разработанные приемы повышения эффективности методов глобального градиентного спуска.

Основная процедура состоит из последовательных итераций, которые совмещают метод последовательных приближений с «инерцией» (по схеме Зейделя) и сдвиг по антиградиенту.

Способы распараллеливания метода. Гибридный алгоритм допускает целый спектр способов распараллеливания.

Способ 1. ДНФ, эквивалентная исходной КНФ делится на п независимых частей (подформул). Для каждой из подформул, с помощью основного алгоритма, ищется вектор решения. Полученные вектора используются в качестве начального приближения для поиска решения следующей подформулы. После нескольких

итераций вычисляется «усредненный» вектор, который используется в качестве начального приближения для поиска решения исходной КНФ.

Способ 2. Может быть реализован при наличии нескольких эквивалентных КНФ с различной структурой. Дело в том, что метод последовательных приближений с «инерцией» формирует различные траектории поиска для КНФ с различной структурой. Это объясняется, например, тем, что в различных КНФ веса одноименных переменных могут различаться. Различные эквивалентные КНФ можно получить, например, с помощью преобразования с применением правил резолюции либо добавлением избыточной информации к исходной КНФ. Вычисления проводятся барабанным методом. Очередное приближение для итерационной процедуры, ассоциированной с одной из КНФ, подставляется в качестве начального приближения итерационной процедуры, ассоциированной со следующей КНФ. Процедура повторяется до тех пор, пока не будет найден выполняющий набор для одной из КНФ.

В третьей главе проводится анализ разработанного метода последовательных приближений с «инерцией». Приводятся результаты испытания метода и его модификаций на различных типах задач. Основное внимание уделяется задаче ВЫПОЛНИМОСТЬ, ассоциированной с задачей факторизации чисел больших размерностей. Показано, что метод может быть с успехом применен к другим задачам информатики.

Для проведения численных экспериментов было отобрано по 500 экземпляров тестовых примеров для каждого типа выбранных генераторов КНФ. Всего около 5000 тестовых КНФ. Были отобраны следующие генераторы: RTI (КНФ, сформированные случайным образом), BMS (КНФ с минимальным хребтом), CBS (КНФ с хребтом, фиксированного размера), UF (унифицированные случайные 3-КНФ), BW (КНФ, ассоциированные с задачей «перекладывание колоды»), GCP (КНФ, ассоциированные с задачей раскраски графов), LPP (КНФ, ассоциированные с задачей логистики), FACTOR (КНФ, ассоциированные с задачей факторизации), DLOG (КНФ, ассоциированные с задачей дискретного логарифмирования), EDLOG (КНФ, ассоциированные с задачей дискретного логарифмирования на эллиптической кривой). Входные параметры алгоритмов сведения задач криптоанализа выбирались исходя из рекомендуемых соответствующими стандартами условий обеспечения критпостойкости.

После каждой модификации проводилось тестирование метода для определения эффективности проделанных изменений.

Стратегия применения правил резолюции. Для определения эффективности стратегии резолюции были проведены численные эксперименты.

Результаты показывают, что структура выбранных типов тестовых КНФ из библиотеки SATLib, позволяет успешно применять стратегию резолюции. Почти всегда удается разрешить более 40% переменных и уменьшить число дизъюнктов КНФ до 50%, что приводит к очень быстрому (за 5-10 итераций) поиску точного решения методом последовательных приближений с «инерцией». В то же время,

на синтезированных (не основанных на прикладных задачах) тестовых примерах данная стратегия практического эффекта не дает.

В применении к КНФ, ассоциированных с задачей факторизации (размерность факторизуемого числа до 1024 бит включительно), показано, что с помощью стратегии резолюции можно разрешать до 1,1% переменных и сокращать до 67% дизъюнктов исходной КНФ. Как показал эксперимент, трудоемкость по времени данной стратегии с глубиной рекурсии 1 кубическая от количества бит в факторизуемом числе.

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

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

Переход к задаче 3-ВЫПОЛНИМОСТЬ. Данные вычислительных экспериментов по увеличению размерности КНФ в процентах от исходного числа дизъюнктов при сведении к 3-КНФ до и после предварительного применения метода резолюции показывают, что увеличение количества дизъюнктов в основном приемлемо. Хотя, размерность для некоторых типов задач увеличивается значительно, что приводит к значительному расширению области поиска решения.

Добавление весовых множителей (регуляризация). Добавление весовых множителей позволяет увеличить эффективность метода последовательных приближений с «инерцией». Хотя методики для определения оптимального набора весовых множителей разработано не было, тем не менее, ясен тот факт, что число решенных тестов стабильно уменьшается при последовательном уменьшении числа «левых» весовых множителей в наборе (параметр К из (4)).

Сдвиг по антиградиенту. Сдвиг по антиградиенту хорошо сокращает погрешности и ускоряет сходимость алгоритма. Число решенных примеров увеличилось примерно на 20%. Применение исключительно только данного приема позволило достаточно эффективно решать тестовые задачи из библиотеки 8АТ1лЬ, например, для КНФ серии №20-91 удалось решить 703 теста из 1000. На примерах иР250-1065 алгоритм показал результат 6% от количества тестов (версия алгоритма без сдвига — 1%). На остальных тестах метод зацикливается в одной из областей локального минимума, что говорит о необходимости применения инструментов обхода локальных минимумов.

Метод смены траектории и туннелирование. Метод смены траектории и туннелирования (в качестве инструмента обхода локальных минимумов) значительно увеличивает число решаемых примеров. Удалось решить 100% тестов библиотеки БАТУЬ за время сравнимое с лучшими решателями 2005 года.

Сравнительные результаты тестирования метода последовательных приближений с «инерцией» со всеми модификациями приведены в таблице 1.

Таблица I. Гибридный метод последовательных приближений с «инерцией» — сравнительные результаты численных экспериментов для задач библиотеки БАИлЬ.

Количество Количество Число Время решен Время Время

литералов (N) дизъюнктов (М) КНФ МППИ решения решения

группе RANOV SATz

В\У (КНФ, ассоциированные с задачей «перекладывание колоды») 48<Ы<6325 |261<М<131973 7 23 сек. |2,20 мин. 2,03 мин.

BMS (КНФ с минимальным хребтом)

100 ¡<430 1000 беек.

CBS (КНФ с хребтом, фиксированного размера)

12 сек.

6 сек.

100

449

2000

5 сек.

4 сек.

12 сек.

UF (унифицированные случайные 3-КНФ) 250 11 065 100

9,82 мин.

3 сек.

19 сек.

,GCP (КНФ, ассоциированные с задачей раскраски графов)

600 ¡2237 100 11,23 мин.

GCP2 (КНФ, ассоциированные с задачей раскраски графов)

2 сек.

0.5 сек.

500

3100

101

2 сек.

4 сек.

2 сек.

Обозначения полей:

Время решения МППИ — среднее время, затраченное на решение всей группы примеров мето,Е последовательных приближений с «инерцией». Время решения ЯЛЫОУ — среднее время, затраченное на решение всей группы приме[ неполным алгоритмом локального поиска ИАЫОУ (победитель соревнований решателей 2( года)

Время решения 5АТг — среднее время, затраченное на решение всей группы примеров полн (переборным) алгоритмом локального поиска БАТг (4-е место на соревнованиях решателей 2( года)_

Определение наиболее вероятных значений верных бит множителей в задаче факторизации. В исследованиях особое внимание уделяется задаче факторизация. Предложены дополнительные методики, увеличивающие эффективность метода в применении к КНФ, эквивалентных задаче факторизация. Среди них эквивалентные преобразования исходной КНФ путем добавления избыточной информации, известной о задаче априори.

1. Так, алгоритм представления задачи факторизация в виде КНФ, предложенный В.И. Дулькейтом кодирует операцию умножения простого числар на простое число q классическим «столбиком». Без потери общности к условиям задачи факторизации числа p-q = q-р можно добавить логическое ограничение (р > q) л (q < р). Представляя данное ограничение в виде КНФ и добавляя (знаком конъюнкции) к исходной КНФ получим эквивалентную формулу с избыточной информацией.

2. Рекомендующие документы по выбору параметров при генерации криптографических ключей для алгоритма RSA устанавливают необходимость выбора простых сомножителей р и q для формирования открытого ключа n-p-q. Информация п mod г ф 0, где г = 2,3,5,7,11,... легко проверяется.

Условие неделимости факторизуемого числа на выбранные числа записывается в виде КНФ и добавляется (знаком конъюнкции) к исходной КНФ.

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

Вторая модификация позволяет увеличить частоту переменных, отвечающих значимым битам искомых множителей, и таким образом «улучшить» характеристики функционала. Исследования показали, что такие формулы, обработанные методом резолюции, решаются до 50% быстрее по сравнению с исходными формулами. Если метод резолюций не применять, то размерность КНФ становиться очень большой.

Сравнительные результаты работы отобранных решателей на тестовых КНФ, ассоциированных с задачей факторизации, приводятся в таблице 2.

Таблица 2. Гибридный метод последовательных приближений с «инерцией» — сравнительные результаты численных экспериментов для задач ВЫПОЛНИМОСТЬ, эквивалентных задаче факторизация.

Число бит в факгории- Кол-во переменных Кол-во Время решения дизъюнктов МППИ (мин) Время решения ЯАШУ (мин) Время решения 5АТг (мин)

зуемом числе

16 3001 156 0,0001 0,0000 0,0083

20 4983 245 0,0005 0,1922 0,0180

24 7457 354 0,0031 0,3174 0,1255

28 10435 483 0,0340 > 60,0000 30,2568

32 13901 632 0,1183 > 60,0000 > 60,0000

36 17871 801 0,0881 > 60,0000 > 60,0000

40 22333 990 1,8817 > 60,0000 > 60,0000

44 27291 1199 10,6301 > 60,0000 > 60,0000

48 32745 1428 61,9942 > 600,0000 > 600,0000

52 38691 1677 487,4967 > 600,0000 > 600,0000

56 45137 1946 11,3225 > 600,0000 > 600,0000

60 52079 2235 4959,6667 > 6000,0000 > 6000,0000

72 75885 3222 11520,0028 > 60000,0000 > 60000,0000

Обозначения полей:

Время решения МППИ — среднее время, затраченное на решение всей группы примеров метод] последовательных приближений с «инерцией».

Время решения ИАЫОУ — среднее время, затраченное на решение всей группы приме] неполным алгоритмом локального поиска ЯАМОУ (победитель соревнований решателей 2( года)

Время решения БАТг — среднее время, затраченное на решение всей группы примеров полн (переборным) алгоритмом локального поиска 8А.Тг (4-е место на соревнованиях решателей 2( года) Знак «>» означает, что за указанное время решение найдено не было.

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

по 100 независимых примеров размерностей 1024, 2048, 3072 бит. Результаты показывают стабильное формирование 68% верных бит при росте размерности задачи. При этом величина доверительного интервала по всем размерностям не превышает 0,18. Максимальное (минимальное) число совпадающих бит так же стабильно - 68,3% (67,7%). При этом число верно определенных бит, отвечающих именно битам сомножителей равно 67,9%. При этом, результат достигается всего за 100-500 итераций, стартуя со случайно сформированного приближения. Отметим, что найденные переменные являются ключевыми для решения задачи, т.е. после подстановки их верных значений в исходную КНФ, формула оказывается легко разрешимой относительно оставшихся переменных. Дополнительно, в работе предложена система тестов, основанная на проверке обстоятельства кластеризации ненулевых строк в матрице умножения классическим «столбиком» в двоичной системе счисления. Тесты позволяют с вероятностью 0.8 определить до 31% конкретных неизвестных в задаче факторизации размерности 512 бит.

Полученные результаты позволяют сделать следующее заключение.

Разработаны и обоснованы методики, равномерно улучшающие сходимость метода последовательных приближений с «инерцией» на всех типах задач ВЫПОЛНИМОСТЬ. Эффективность гибридного метода не уступает эффективности «лучших» решателей 2005 года.

Разработана стратегия применения правил резолюции. Исследована и подтверждена эффективность использования стратегии резолюции как препроцессора КНФ в методе последовательных приближений с «инерцией».

Исследована применимость метода последовательных приближений с «инерцией» к КНФ, ассоциированным с задачами криптоанализа асимметричных шифров.

Для КНФ, эквивалентных задаче факторизации (с соблюдением всех условий криптостойкости RSA) размерностью до 72 бит были получены точные решения. При этом эффективность предложенного метода превосходит многие решатели задачи ВЫПОЛНИМОСТЬ. Приближения, формируемые методом, более чем на 68% совпадают с решением независимо от размерности задачи (до 3072 бит включительно), причем с ростом размерности наблюдается рост доли совпадающих компонент вектора приближения. Кроме того, разработана система дополнительных тестов, позволяющая с высокой долей вероятности определять конкретные биты сомножителей в задаче факторизации.

Список опубликованных работ

в ведущих рецензируемых научных изданиях, определенных Высшей аттестационной комиссией:

1. Дулькейт В.И., Файзуллин Р.Т., Хныкин И.Г. Алгоритм минимизации функционала, ассоциированного с задачей 3-SAT и его практические применения // Компьютерная оптика, т. 32, №1. - 2008. - С.68-73.

2. Дулькейт В.И., Файзуллин Р.Т. Хныкин И.Г. Метод решения задачи ВЫПОЛНИМОСТЬ и его применение для криптографического анализа асимметричных шифров // Доклады Томского государственного универистета систем управления и радиоэлектроники. - 2008. - ч. 1.2(18). - С.54-56.

3. Дулькейт В.И., Файзуллин Р.Т., Хныкин И.Г. Непрерывные аппроксимации решения задачи ВЫПОЛНИМОСТЬ применительно к криптографическому анализу асимметричных шифров II Компьютерная оптика, т. 33, №1. - 2009. - С.86-91.

4. Хныкин И.Г. Эквивалентное преобразование КНФ, ассоциированных с практическими задачами с помощью правил резолюции // Системы управления и информационные технологии, 2(36), 2009. - С. 54-58.

в других изданиях:

5. Дулькейт В.И., Файзуллин P.E., Хныкин И.Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа асимметричных шифров // Прикладная дискретная математика. - 2008. - № 2. - С. 113-119.

6. Дулькейт В.И., Файзуллин Р.Т., Хныкин И.Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа // Дифференциальные уравнения. Функциональные пространства. Теория приближений. Тез. докл. Международная конференция, посвященная 100-летию со дня рождения С.Л. Соболева. - Новосибирск: Ин-т математики СО РАН, 2008. - С.484-485.

7. Дулькейт В.И., Файзуллин Р.Т., Хныкин И.Г. Сведение задач криптоанализа асимметричных шифров к решению ассоциированных задач ВЫПОЛНИМОСТЬ // Сборник докладов XIII Всероссийской конференции «Математические методы распознавания образов». - М.: МАКС Пресс, 2007. - С.249-251.

8. Хныкин И.Г. Алгоритм минимизации функционала ассоциированного с задачей 3-SAT // Проблемы теоретической и прикладной математики: Труды 38-й Региональной молодежной конференции. - Екатеринбург: УрО РАН, 2007. - С.427-432.

9. Хныкин И.Г. Алгоритм минимизации функционала, ассоциированного с задачей SAT // Труды 13-й Всероссийской конференции «Математическое программирование и приложения», Информационный бюллетень АМП №11. (Тез. докл. Всерос. конф.) - Екатеринбург: УрО РАН, 2007.

10. Хныкин И.Г. Эквивалентное преобразование КНФ, ассоциированных с задачами криптографического анализа, с помощью правил резолюции // Прикладная дискретная математика, приложение. (Тез. докл. конф. SIBECRYPT09) - Томск: ТГУ, 2009.

Подписано в печать 12 ноября 2009 г. Формат 60x84/16 Тираж 100 экз. Отпечатано с готового оригинала-макета 443086, г.Самара, Московское шоссе, 34, СГАУ

Введение.

Глава 1. Задача ВЫПОЛНИМОСТЬ и методы ее решения.

1.1. Постановка задач.

1.2. Математические модели задачи ВЬШОЛНИМОСТЬ.

1.3. Алгоритмы поиска решения задачи ВЫПОЛНИМОСТЬ.

1.3.1. Алгоритм DP (Davis-Putnam).

1.3.2. Алгоритм DPLL (Davis-Putnam-Logemann-Loveland).

1.3.3. Методы локального поиска.

1.3.4. Методы преодоления локальных экстремумов.

1.3.5. Семейство алгоритмов локального поиска с обходом локальных минимумов.

1.3.6. Семейство градиентных алгоритмов локального поиска.

1.3.7. Методы глобальной оптимизации.

1.3.8. Непрерывный метод Лагранжа.

Глава 2. Описание гибридного метода последовательных приближений с «инерцией» в применении к задаче ВЫПОЛНИМОСТЬ.

2.1. Переход от задачи ВЬШОЛНИМОСТЬ к задаче поиска глобального минимума.

2.2. Построение метода последовательных приближений с «инерцией».

2.3. Модификации и гибридизации метода последовательных приближений с «инерцией».

2.3.1. Переход к задаче 3-ВЬШОЛНИМОСТЬ.

2.3.2. Стратегия применения правил резолюции.

2.3.3. Выбор начального приближения.

2.3.4. Добавление весовых множителей.•.

2.3.5. Сдвиг по антиградиенту.

2.3.6. Туннелирование.

2.3.7. Метод смены траектории.

2.3.8. Рестарт.

2.3.9. Выбор метода проектирования.

2.3.10. Увеличение разрядности.

2.3.11. Гибридный метод последовательных приближений с «инерцией».

2.3.12. Способы распараллеливания метода.

Глава 3. Результаты численных экспериментов применения модифицированного метода последовательных приближений с «инерцией» к различным типам задач ВЬШОЛНИМОСТЬ.

3.1. Задачи для тестирования метода последовательных приближений с инерцией» и его модификаций.

3.1.1. Тестовые примеры открытой библиотеки SATLib.

3.1.2. Задачи криптографического анализа несимметричных шифров.

3.2. Результаты численных экспериментов гибридного метода последовательных приближений с «инерцией».

3.2.1. Стратегия применения правил резолюции.

3.2.2. Переход к задаче 3-ВЫПОЛНИМОСТЬ.

3.2.3. Добавление весовых множителей.

3.2.4. Сдвиг по антиградиенту.

3.2.5. Метод смены траектории и туннелирование.

3.2.6. Увеличение разрядности.

3.2.7. Гибридный метод последовательных приближений с «инерцией».

3.2.8. Способы распараллеливания метода.

3.3. Исследование применимости метода последовательных приближений с «инерцией» к задаче факторизации.

3.3.1. Определение наиболее вероятных значений бит сомножителей.

3.3.2. Выбор начального приближения.

Задача ВЫПОЛНИМОСТЬ — одна из наиболее интересных задач информатики.

В 1936 году Эмиль Пост (Emil Leon Post), а в 1937 году - Алан Тьюринг (Alan Turing) независимо друг от друга разработали теоретическую модель вычислительной машины, которая легла в основу теории алгоритмов. Она представляет собой бесконечную в одну сторону ленту, по которой передвигается одна — единственная головка. Каждая ячейка ленты может находиться в одном из состояний: ноль, единица, а также в неопределенном состоянии. На каждом шаге выполнения алгоритма головка может сдвинуться влево, сдвинуться вправо либо записать в ячейку, над которой она находится, ноль или единицу. Программа для такой машины — это сколь угодно большой, но конечный набор состояний, каждому из которых соответствует некоторое действие, а также следующее состояние. Есть два выделенных состояния — исходное, в котором начинается работа программы, и специальное состояние СТОП, которое соответствует выходу из программы.

Эта модель вычислений, получившая название детерминированной машины Тьюринга, стала общепринятой (хотя Пост придумал свою модель на год раньше). В информатике широко известно нестрогое утверждение (так называемый тезис Чёрча), которое гласит, что любой объект, отвечающий нашему интуитивному понятию алгоритма, можно реализовать в виде программы на машине Тьюринга. Контрпримеров к этому утверждению пока не обнаружено, и оно считается верным — хотя доказать его невозможно.

Класс задач, которые решаются за полиномиальное время на детерминированной машине Тьюринга, называют классом Р.

Другой класс задач — которые решаются за полиномиальное время на, так называемых, недетерминированных машинах Тьюринга, называют классом NP. Для наглядности приведем следующее описание: задача входит в класс NP, если существует детерминированная машина Тьюринга «с подсказкой», которая по данной ей подсказке сможет за полиномиальное время либо дать положительный ответ и не ошибиться, либо дать отрицательный ответ с возможной ошибкой. При этом для каждого набора данных, ответ на который положителен, должна существовать подсказка, которую примет эта машина Тьюринга.

Проблема Р называется NP-полной, если Р принадлежит NP и любая задача из NP может быть сведена к задаче Р за полиномиальное время.

Исторически первой из известных NP-полных задач была задача ВЫПОЛНИМОСТЬ (ее полноту доказал Стивен Кук (Stephen Cook) [27]). Это и обусловило ее фундаментальность. Иными словами, существование полиномиального алгоритма решения задачи ВЫПОЛНИМОСТЬ влечет разрешение теоретической проблемы P=NP. Сегодня задача ВЫПОЛНИМОСТЬ занимает первое место в списке избранных NP-полных задач.

На практике, задача ВЫПОЛНИМОСТЬ является фундаментальной для решения многих проблем информатики: искусственного интеллекта, проектирования компьютерных систем, роботостроения, криптографии и других. Тема сведения задач из различных областей прикладной математики и информатики к задаче ВЫПОЛНИМОСТЬ хорошо развивается. В России этому посвящены работы Семенова А.А., Буранова Е.В., за рубежом известны работы Kautz Н. Selman В. [3], [85], [84], [51]. Одна из причин этого — возможность решать задачи, возникающие в самых различных областях, единым алгоритмом решения задачи ВЫПОЛНИМОСТЬ.

Перспективным направлением в поиске алгоритмов решения задачи ВЫПОЛНИМОСТЬ представляется и сведение КНФ к непрерывному аналогу, к задаче поиска точек глобального минимума ассоциированного функционала с применением богатого арсенала вычислительной математики и математического анализа.

Цель работы.

Целью данной диссертационной работы является построение и исследование непрерывных моделей задачи ВЫПОЛНИМОСТЬ и исходя из этого построение эффективного метода решения задачи.

Актуальность работы.

Возможность сведения задач факторизации, дискретного логарифмирования, дискретного логарифмирования на эллиптической кривой к задаче ВЫПОЛНИМОСТЬ делает разработку моделей и алгоритмов решения особенно актуальной. Ведь данные задачи лежат в основе алгоритмов криптографической обработки данных. А, в настоящее время, криптографический анализ имеет громадное практическое значение, так как гарантированно стойкие алгоритмы шифрования являются основой надежности современных систем телекоммуникаций и систем финансовых взаиморасчетов. С теоретической стороны, прогресс в области криптографического анализа сопровождается бурным развитием смежных областей математики и информатики.

Основным подходом проверки криптографической стойкости асимметричных шифров в настоящее время являются алгоритмы числового решета в поле чисел общего вида [53] и различные модификации алгоритмов ро - Полларда и лямбда - Полларда, основывающиеся на детерминированном случайном блуждании по группе [51], то есть методы требуют привлечения обширного математического аппарата. Сообщения появляющиеся время от времени лишь подтверждают стойкость известных алгоритмов. Например, для факторизации чисел «рабочих» размерностей (-1000 бит) требуется задействовать на несколько месяцев вычислительные мощности кластеров из самых верхних позиций списка Топ-500 [83]. То есть увеличение длины ключа в полтора или два раза решает вопрос о криптостойкости принципиально.

Совершенно новой альтернативой алгебраическому подходу является так называемый логический криптоанализ, когда криптографический алгоритм, рассматривается, как программа для машины Тьюринга и подстановка открытого и шифрованного текстов в эту программу естественным образом приводит к задаче ВЫПОЛНИМОСТЬ для конъюнктивной нормальной формы. Часть выполняющего набора является ключом алгоритма. Идея такого подхода была впервые предложена в 1997 году в работе Cook S. [28], при поиске сложных задач для тестирования решателей КНФ. Сегодня данная тематика представлена в работах Ушакова A. A., Massacci F., Беспалова Д.В., Marraro L., и других.

Как показал опыт, применение переборных алгоритмов, с частью из которых можно ознакомиться в обзоре Gu J. [44], сталкивается с принципиальными трудностями, задачи криптографии (и задачи больших размерностей вообще) оказываются действительно трудными для переборных алгоритмов. Естественно возникает идея перехода к непрерывным моделям, когда поиск выполнимого набора для КНФ осуществляется как поиск экстремума, ассоциированного с КНФ функционала. Впервые эта идея была реализована в работах Маслова С.Ю., Крейновича В.Я. и получила дальнейшее развитие в работах R.Sosic, J.Gu, A.Tora, A.Zilinskas [13], [14], [70], [69], [72]. Обратим внимание на то, что хотя существенных успехов на данный момент еще нет, но имеется принципиальное отличие непрерывных методов от переборных алгоритмов поиска, — сдвиг по антиградиенту происходит по всем переменным сразу. Кроме того, для многих задач, априори известно, что глобальный минимум функционала единственен и в случае, когда локальных минимумов и других особых точек нет, минимизация происходит эффективно.

С другой стороны, достаточно очевидно, что нет необходимости в том, чтобы «точно» определить все биты ключа. Достаточно той информации, что набор бит, или ключа, или множества бит, однозначно определяющего ключ, совпадает с точным решением с вероятностью значимо большей, чем 0.5. А в результате применения итерационных методов можно надеяться на то, что мы сможем «подобраться» к такой окрестности достаточно близко. Таким образом, проверка известных в настоящее время криптографических алгоритмов на стойкость к поиску глобального экстремума является новым и необходимым тестом.

Содержание работы.

Диссертационная работа состоит из введения, трех глав, заключения, библиографии, двух приложений.

Заключение

В работе проводятся исследования задачи ВЫПОЛНИМОСТЬ на основе математических моделей минимизации специальным образом построенного функционала.

Среди основных результатов диссертации можно отметить следующие:

1. Разработаны и обоснованы методики, равномерно улучшающие сходимость метода последовательных приближений с «инерцией» на всех типах задач ВЫПОЛНИМОСТЬ. Эффективность гибридного метода не уступает эффективности «лучших» решателей 2005 года.

2. Разработана стратегия применения правил резолюции. Исследована и подтверждена эффективность использования стратегии резолюции как препроцессора КНФ в методе последовательных приближений с «инерцией».

3. Исследована применимость метода последовательных приближений с «инерцией» к КНФ, ассоциированным с задачами криптоанализа асимметричных шифров.

4. Для КНФ, эквивалентных задаче факторизации (с соблюдением всех условий криптостойкости RSA) размерностью до 72 бит были получены точные решения. При этом эффективность предложенного метода превосходит известные нам решатели задачи ВЫПОЛНИМОСТЬ. Приближения, формируемые методом, более чем на 68% совпадают с решением независимо от размерности задачи (до 3072 бит включительно), причем с ростом размерности наблюдается рост доли совпадающих компонент вектора приближения. Кроме того, разработана система дополнительных тестов, позволяющая с высокой долей вероятности определять конкретные биты сомножителей в задаче факторизации.

1. Бахвалов Н.С. Численные методы. - М.: Бином. Лаборатория знаний, 2007. -627 с.

2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982. 579 с.

3. Дулькейт В.И. КНФ представления для задач факторизации и дискретного логарифмирования // Проблемы теоретической и прикладной математики: Труды 38-й Региональной молодежной конференции. Екатеринбург: УрО РАН,2007. С.350-355.

4. Дулькейт В.И., Файзуллин Р.Е., Хныкин И.Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа асимметричных шифров // Прикладная дискретная математика. 2008. - № 2. - С.113-119.

5. Дулькейт В.И., Файзуллин Р.Т. Хныкин И.Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа. // Доклады Томского государственного универистета систем управления и радиоэлектроники. 2008. -ч. 1.2(18). -С.54-56.

6. Дулькейт В.И., Файзуллин Р.Т., Хныкин И.Г. Алгоритм минимизации функционала, ассоциированного с задачей 3-SAT и его практические применения // Компьютерная оптика, т. 32, №1. 2008. - С.68-73.

7. Дулькейт В.И., Файзуллин Р.Т., Хныкин И.Г. Непрерывные аппроксимации решения задачи ВЫПОЛНИМОСТЬ применительно к криптографическому анализу асимметричных шифров // Компьютерная оптика, т. 33, №1. 2009. -С. 86-91

8. Ершов Ю. Л., Палютин Е. А. Математическая логика. М.: Наука, 1987.

9. Кочетков Е.С., Смерчинская С.О., Соколов В.В. Теория вероятностей и математическая статистика. М.: Форум. Профессиональное образование, 2008. -240 с

10. Крейнович В.Я. Семантика итеративного метода С.Ю. Маслова // Вопросы кибернетики. Проблемы сокращения перебора. М.: АН. СССР, 1987. - С. 30-62.

11. Маслов С. Ю. Итеративные методы в переборной модели как модель интуитивных // Тезисы IX Всесоюзной конференции по кибернетике. 1981. -С.26-28.

12. Прикладная статистика. Учебник. / А.И.Орлов.- М.: Издательство «Экзамен», 2004. 656 с.

13. Файзуллин Р. Т. О решении нелинейных алгебраических систем гидравлики // Сибирский журнал индустриальной математики. 1999. - №2. -С. 176-184.

14. Хныкин И.Г. Модификации КНФ, эквивалентным задачам криптоанализа асимметричных шифров методом резолюции // Информационные технологии моделирования и управления. 2007. №2. - С.328-337.

15. Хныкин И.Г. Алгоритм минимизации функционала ассоциированного с задачей 3-SAT // Проблемы теоретической и прикладной математики: Труды 38-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2007. -С.427-432.

16. Хныкин И.Г. Эквивалентное преобразование КНФ, ассоциированных с задачами криптографического анализа, с помощью правил резолюции // Прикладная дискретная математика, приложение. (Тез. докл. конф. SIBECRYPT'09) Томск: ТГУ, 2009.

17. Billionnet A., Sutter A. An efficient algorithm for 3-satisfiability problem // Operations Research Letters 12. 1992. - P.29-36.

18. Blum L., Blum M., Shub M. A Simple Unpredictable Pseudo-Random Number Generator // SIAM Journal on Computing. 1986. - Vol. 15., P.364-383.

19. Bugrara K., Purdom P. Clause order backtracking // Technical Report 311. -1990.-P. 17-26.

20. Buro M., Biining H.K. Report on a SAT competition // Bulletin of the European

21. Association for Theoretical Computer Science. 1993. - 49. - P. 143-151.

22. Cha В., Iwama K. Adding new clauses for faster local search // In Proceedings of AAAI-96. 1996. - P.332-337.

23. Cook S.A. The complexity of theorem proving procedures // Proceedings of the Third Annual ACM Symposium on Theory of Computing. 1971. - P.151-158.

24. Cook S.A., Mitchel D.G. Finding hard instances for the satisfiability problem // A survey. DIMACS series in discrete mathematics and theoretical computer science. -1997. Vol.5. - 151 p.

25. Davis M., Logemann G., Loveland D. A Machine Program for Theorem Proving // Communications of the ACM. 1962. - 5(7). - P.394-397.

26. Davis M., Putnam H. A Computing Procedure for Quantification Theory // Journal of the ACM. 1960. - 7(3). - P.201-215.

27. Doyle J. A truth maintenance system // Artificial Intelligence. 1979. - 12. -P.231-272.

28. Franco J. Elimination of infrequent variables improves average case performance of satisfiability algorithms // SIAM J. on Computing. 1991. - 20. - P.ll 19-1127.

29. Freuder E.C. Quinn M.J. Taking advantage of stable sets of variables in constraint satisfaction problems // In Proceedings of 9th IJCAI. 1985. - P.1076-1078.

30. Galil Z. On resolution with clauses of bounded size // SIAM Journal on Computing. 1977. - 6. - P.444-459.

31. Gent I., Walsh T. Towards an understanding of hill-climbing procedures for SAT // In Proceedings of AAAI-93. 1993. - 17 p.

32. Gu J. Global optimization for satisfiability (SAT) problem // IEEE Trans, on Knowledge and Data Engineering. 1994. - 6(3)Jun. - P.361-381.

33. Gu J. On Optimizing a Search Problem // In N. G. Bourbakis, editor, Artificial Intelligence Methods and Applications. 1992. Vol.1, chapter 2. - P.63-105.

34. Gu J. Efficient local search for very large-scale satisfiability problem // SIGART Bulletin. 3(1).Jan. - ACM Press, 1992. - P.8-12.

35. Gu J. Parallel algorithms and architectures for very fast search // Ph.D thesis.

36. Technical Report UUCS-TR-88-005. 1988. - 7 p.

37. Gu J. Local search for satisfiability (SAT) problem // IEEE Trans, on Systems, Man, and Cybernetics. 1993. - 23(4)Jul. - P. 1108-1129.

38. Gu J. How to solve Very Large-Scale Satisfiability problems // Technical Report UUCS-TR-88-032. 1988. - 6 p.

39. Gu J., Gu Q.P. Average time complexities of several local search algorithms for the satisfiability (SAT) problem // Technical Report UCECE-TR-91-004. 1991. -Vol. 834.-P. 146-154.

40. Gu J., Lizhoudu. An efficient implementation of the SAT 1.5 algorithm // Technical Report, USTC. 1995. - 11 p.

41. Haken, A. The intractability of resolution // Theoretical Computer Science. -1985.-39.-P. 142-150.

42. Hansen E. R. Global optimization using interval analysis / M. Dekker. N.Y., 1992.-20 p.

43. Horst R., Tuy H. Global Optimization: Deterministic Approaches // Springer, Verlag. Berlin, 1990. - 22 p.

44. Jeroslow R.E., Wang J. Solving prepositional satisfiability problems // Annals of Mathematics and AI. 1990. - 1. - P. 167-187.

45. Johnson D.S. Approximation Algorithms for Combinatorial Problems // Journal of Computer and Systems Sciences. 1974. - 9. - P.256-278.

46. Kautz H., Selman B. Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search //Proc. AAAI-96. 1996. - P.1194-1201.

47. Koblitz N., Menezes A., Vanstone S. The state of elliptic curve cryptography // Designs Codes and Cryptography. 2000. - 19. - P.l73-193.

48. Kodandapani K.L., McGrath E.J. A wirelist compare program for verifying VLSIlayouts // IEEE Design and Test of Computers. 1986. - 3(3). - P.46-51.

49. Lenstra A., Lenstra H. The Development of the Number Field Sieve // Springer, Verlag. Berlin, 1993. - 23 p.

50. Levin L. Universal search problems // Problems of Information Transmission. -1984. -9(3). -P.265-266.

51. Lieberherr K.J., Specker E. Complexity of partial satisfaction // Journal of ACM. 1981.-28. -P.411-421.

52. Minton S., Johnston M.D., Philips A.B., Laird P. A heuristic repair method for constraint satisfaction and scheduling problems // Artificial Intelligence. 1992. - 58. -P. 161-205.

53. Ouyang Ming How Good Are Branching Rules in DPLL? // Discrete Applied Mathematics. 1998. - 89(1-3). - P.281-286.

54. Pardalos P.M., Rosen J.B. Constrained Global Optimization: Algorithms and Applications // Springer, Verlag. N.Y., 1987. - 23 p.

55. Petrie C. Revised dependency-directed backtracking for default reasoning // In Proceedings of АААГ87. 1987. - P. 167-172.

56. Prestwich S., Lynce I. Refutation by Randomized General Resolution // Twenty-Second Conference on Artificial Intelligence (AAAI), Nectar Track. 2007. - 217 p.

57. Purdom P.W., Haven G.N. Backtracking and probing // Technical Report No. 387, Dept. of Computer Science, Indiana University. 1993. - 17 p.

58. Robinson J.A. A machine-oriented logic based on the resolution principle // Journal of the ACM. 1965. - 12. - 111 p.

59. Saab Y.C., Rao V.B. Combinatorial optimization by stochastic evolution // IEEE Transactions on CAD. 1991. - CAD-10(4), Apr. - P.525-535.

60. Schwartzschild B.M. Statistical mechanics algorithm for Monte Carlooptimization // Physics Today. 1982. - 35. - P. 17-19.

61. Selman В., Levesque H., Mitchell D. A new method for solving hard satisfiability problems // In Proceedings of AAAI'92, Jul. 1992. P.440-446.

62. Shapiro, S. S. and Wilk, M. B. (1965). "An analysis of variance test for normality (complete samples)", Biometrika, 52, 3 and 4, pages 591-611.

63. Singer J., Gent I., Smaill A. Backbone Fragility and the Local Search Cost Peak // Journal of Artificial Intelligence Research. 2000. - 12. - P.235-270.

64. Sosic R., Gu J. Efficient local search with conflict minimization // IEEE Trans, on Knowledge and Data Engineering. 1994. 6(5). - P.661-668.

65. Sosic R., Gu J. Fast search algorithms for the n-queens problem // IEEE Trans, on Systems, Man, and Cybernetics. 1991. - SMC-21(6), Nov./Dec. - P. 1572-1576.

66. Stallman R., Sussman G.J. Forward reasoning and dependency directed backtracking. Artificial Intelligence. 1977. - Vol.9(2). - P.135-196.

67. Torn A., Zilinskas A. Global Optimization // Springer,Verlag. N.Y., 1989. - 20 p.

68. Tseitin G.S. On the Complexity of Derivations in Prepositional Calculus // Structures in Constructive Mathematics and Mathematical Logic, A.O. Slisenko, ed. -1968. Part II. - P. 115-125.

69. Urquhart A. Hard examples for resolution // Journal of the Association for Computing Machinery. 1987. - Vol.34. - P. 215-225.75. \vww.maplesoft.com/support/help/view.aspx?path=Statistics/ShapiroWilkWTest