Введение к работе
Объект исследования и актуальность работы. Базис Грёбнера представляет собой каноническую форму системы алгебраических [1], дифференциальных [2, 3] или разностных [4] многочленов многих переменных. Приведение систем таких многочленов к данной канонической форме является наиболее универсальным алгоритмическим подходом к их исследованию и решению.
Так, построение базиса Грёбнера для системы алгебраических уравнений полиномиального типа позволяет установить её совместность (т.е. наличие общих корней у многочленов системы), определить число (а в случае бесконечного числа — размерность пространства) решений, привести исходную систему к треугольному виду, либо исключить часть переменных. В целом метод базисов Грёбнера является обобщением метода Гаусса на случай нелинейных систем.
Алгоритмически задача нахождения базиса Грёбнера для заданной системы многочленов в коммутативной алгебре была решена около полувека назад Б.Бухбергером [1], а соответствующий алгоритм [5] получил имя автора. С тех пор усилиями многих исследователей базисы Грёбнера нашли плодотворное применение в различных областях математики и естественных наук и в настоящее время обладают обширным числом практических приложений [6].
Расширение области применения базисов Грёбнера не обошло стороной и специфический случай систем булевых многочленов. Впервые алгоритм вычисления булевых базисов Грёбнера был представлен в [7]. Теоретическим фундаментом идеи использования базисов Грёбнера в булевых кольцах послужила весьма развитая к тому времени теория булевых функций.
Напомним, что n—местной булевой функцией называется отображение { 0,1}n в { 0,1} [8]. Для булевых функций определено понятие их суперпозиции, и, как следствие, для любого множества булевых функций может быть получено его замыкание — как множество всех функций, получаемых с помощью суперпозиции из функций исходного множества. В таком случае говорят, что множество Q порождает замкнутый класс булевых функций R: [Q] = R (замкнутый, т.к. очевидно, что [[R]] = [R]). Если [R] совпадает со множеством всех булевых функций, то порождающее множество Q называют полным. Базисом замкнутого класса R в теории булевых функций называют такое множество Q, которое порождает класс R, но при этом ни одно несобственное подмножество Q этого класса не порождает.
Известно, что множество булевых функций {1,x + y, xy} полно [8] (здесь 1 — функция-константа единица, x + y — сложение по модулю 2, xy — конъюнкция). Причем функции x + y и xy являются соответственно сложением и умножением в поле Галуа F2 = {0,1}. Поэтому, пользуясь коммутативностью сложения и умножения, дистрибутивностью умножения относительно сложения и соотношениями x + x = 0, x x = x, всякую функцию из замыкания множества {1,x + y,xy} (т.е. любую булеву функцию) можно представить в виде многочлена Жегалкина [8]:
^ ^ ail---is xil xis , (i1 ,---,is)
где ail---is Є F2. В данной работе мы будем называть многочлен Жегалкина булевым многочленом. Все такие многочлены от заданного конечного набора переменных {xi, ,xn} образуют кольцо, которое мы будем называть булевым. Это кольцо является эквивалентом булевой алгебры [9]. Более того, каждая булева функция представима булевым многочленом единственным образом [8]. Как и в случае булевых функций, множество булевых многочленов порождает идеал в булевом кольце, причем булево кольцо является кольцом главных идеалов, т.е. каждый идеал кольца порождается его единственным
элементом.
Базисы Грёбнера в целом, как уже было сказано, и булевы в частности, оказываются весьма полезными в случаях, когда решение некоторой задачи связано с исследованием и/или решением соответствующей полиномиальной системы [10-12]. В случае булева кольца наиболее распространенными задачами такого рода являются задачи криптоанализа и булевой выполнимости. Например, одним из первых ярких применений метода булевых базисов Грёбнера стало решение сложной [13] проблемы — криптосистемы на скрытых отображениях полей (Hidden Fields Equations) в криптографии с открытым ключом. Эта задача описывается системой квадратичных булевых многочленов от 80 переменных, и впервые ее решение было получено именно путем вычисления булева базиса Грёбнера с помощью алгоритма F5, позднее — с помощью алгоритма F4 [14, 15].
Задача булевой выполнимости SAT (Boolean Satisfiability) — очень распространенная и, в общем случае, MV-полная [16] задача, которая возникает, в частности, при проверке корректности работы оборудования и программ, в робототехнике, при создании экспертных систем и т.п. Для решения этой задачи разработан ряд успешных и широко применяемых специализированных алгоритмов. В настоящее время уже известен ряд примеров [17] успешного применения техники булевых базисов Грёбнера к решению задачи булевой выполнимости. Через 12 лет после теоретического обоснования [18] применимости таких базисов для решения задач SAT был создан программный пакет PolyBoRi [19], использующий метод базисов Грёбнера и способный конкурировать с лучшими современными программами решения задач булевой выполнимости (SAT-solvers).
Приведем простой пример задачи булевой выполнимости, иллюстрирующий применение метода базисов Грёбнера для её решения, т.е. для ответа на вопрос: существует ли для заданной булевой функции такой набор значений переменных, на котором функция принимает значение 1 (истина)? В терминах базисов Грёбнера данный вопрос формулируется следующим образом: состоит ли соответствующий базис Грёбнера из одного многочлена, который, в свою очередь, является единичным булевым мономом {1}) или нет? В последнем случае рассматриваемая задача является выполнимой.
Пусть булева функция, заданная в своей конъюнктивой нормальной форме, имеет вид:
f (x, y,z) = (x У y У z) Л (x У y) Л (y У z) Л (z У x) Л (x У y У z) = fi Л f Л f Л f4 Л f
Приведем функцию к полиномиальному виду, используя следующие формулы:
x Л y —> xy, x У y —> xy + x + y, x —> x + 1
Тогда булева выполнимость рассматриваемой задачи сводится к существованию решения в F2 у системы булевых многочленов
/
fi = xyz + xy + xz + yz + x + y + z + 1 f2 = xy + y < f3 = yz + z f4 = xz + x
f5 = xyz
Вычисление базиса Грёбнера для данной системы многочленов показывает, что этот базис равен {1}, т.е. полиномиальная система не имеет решений (несовместна), и задача невыполнима.
Ещё одним интересным применением булевых базисов Грёбнера может стать моделирование квантовых вычислений, т.е. построение унитарной матрицы квантовой цепи на классическом компьютере. Как показано в [20], для
квантовой цепи с помощью вентилей Тоффоли и Адамара (они образуют универсальный базис вентилей) её цепная матрица однозначно определяется числом общих корней (когда все переменные принимают значения в F2) системы булевых многочленов. В работе [21] описан пакет для системы Mathematica [22], позволяющий пользователю по введенной квантовой цепи строить её цепную унитарную матрицу стандартными методами линейной алгебры, а также автоматически создавать систему определяющих её булевых многочленов. На практике, в силу ограниченности памяти компьютера, методами линейной алгебры удается промоделировать лишь 20-25 кубитные схемы. И хотя задача построения базисов Грёбнера в булевых кольцах имеет экспоненциальную сложность [23], уже сейчас эта задача решается для некоторых систем многочленов от 100 и более переменных [17], что дает реальную надежду на то, что базисы Грёбнера, по крайне мере в отдельных случаях, позволят сильно продвинуться в моделировании квантовых вычислений.
Стоит отметить, что случай полиномиальных систем с коэффициентами из конечного поля F2 интересен не только тем, что имеет огромное количество практических приложений, но и простотой арифметики коэффициентов. Если рассматривать многочлены с коэффициентами из конечных полей большего размера или из поля рациональных чисел, то эффективность реализации операций с такими многочленами в значительной степени определяется эффективностью реализации операций над самими коэффициентами. Обеспечение же последней является отдельной и очень важной темой исследования [24].
Таким образом, можно утверждать, что в настоящее время существует практическая потребность в быстрых и высокоэффективных алгоритмах для вычисления булевых базисов Грёбнера и их реализациях, что заставляет исследователей искать и находить новые, более эффективные алгоритмы для их построения. К таковым можно отнести уже упоминавшиеся алгоритмы F4
и F5 французского математика Фожера, целый ряд модификаций алгоритма F5, например, алгоритмы G2V и GVW [25] — результат работы китайских и американских исследователей, а также инволютивный алгоритм [26, 27] Блинкова и Гердта. Булевой версии последнего и посвящена данная работа.
Цель диссертационной работы. Целью настоящей работы является разработка эффективного алгоритма построения булевых базисов Грёбне- ра для идеала в булевом кольце, порождаемого заданной системой булевых многочленов, а также реализация разработанного алгоритма в виде специализированных пакетов и их встраивание в системы компьютерной алгебры с открытым кодом.
Для достижения поставленной цели решаются следующие основные задачи:
Исследование современных алгоритмов построения базисов Грёбнера в полиномиальных кольцах и условий их применимости для вычисления булевых базисов Грёбнера.
Разработка специализированного алгоритма, способного строить булев базис Грёбнера путем вычислений непосредственно в булевом кольце.
Реализация разработанного алгоритма на языке С++ и ее оптимизация на основе эмпирических данных, полученных с помощью компьютерных экспериментов.
Разработка программных пакетов, реализующих предложенный алгоритм в среде систем компьютерной алгебры с открытым исходным кодом.
Научная новизна. В диссертационной работе получен ряд результатов, обладающих научной новизной:
Разработан новый эффективный алгоритм построения базиса Грёбнера для системы булевых многочленов, который, в отличие от других известных алгоритмов, позволяет проводить вычисления непосредственно в булевом кольце. Доказана завершаемость данного алгоритма за конечное число шагов.
Впервые получена точная верхняя оценка на число элементов редуцированного булева базиса Грёбнера, что важно для оценки возможных затрат памяти на вычисление данного базиса.
В системы компьютерной алгебры с открытым кодом REDUCE (версия 3.8) и Macaulay2 (версия 1.4.1) встроены новые пакеты, которые предназначены для построения булевых базисов Грёбнера и значительно превосходят по своей вычислительной эффективности имевшиеся в этих системах возможности для указанного построения.
Практическая и теоретическая ценность. Разработанный в диссертации алгоритм построения булевых базисов Грёбнера применим для решения ряда актуальных математических и вычислительных задач из различных областей математики и естественных наук, включая криптоанализ, робототехнику, проверку булевой выполнимости, моделирование квантовых вычислений на классических компьютерах, разработку и анализ экспертных систем.
Реализация алгоритма в виде пакета BIBasis встроена в открытые системы компьютерной алгебры Macaulay2 и REDUCE. Это существенно расширяет применимость указанных систем для решения задач, сводящихся к булевой логике. При этом Macaulay2 является одной из наиболее широко используемых программных систем специального назначения, ориентированных на задачи вычислительной коммутативной алгебры и алгебраической геометрии, а REDUCE является системой компьютерной алгебры общематематического назначения и находит применение в различных областях науки и техники.
На защиту выносятся следующие основные результаты и положения:
-
-
Проведено исследование применимости инволютивного алгоритма к задаче построения базисов Грёбнера и базисов Жане в булевом кольце. В результате показано, что инволютивный алгоритм на основе деления Жане, равно как и алгоритм Бухбергера, может быть использован для этой цели только в том случае, когда исходное множество булевых многочленов дополняется множеством всех полевых биномов. После этого вычисление базиса Грёбнера производится в кольце многочленов над полем F2, а искомый булев базис является мультилинейным подмножеством найденного базиса Грёбнера.
-
Разработана версия инволютивного алгоритма на основе деления Пом- маре для построения редуцированных булевых базисов Грёбнера и базисов Поммаре непосредственно в булевом кольце, т.е. без использования полевых мономов. Доказаны корректность и завершаемость данного алгоритма. Показано, что он позволяет эффективно использовать представление булевых многочленов в памяти ЭВМ и простоту их арифметики. Получена точная верхняя оценка на число элементов редуцированного булева базиса Грёбнера.
-
Разработанный булев инволютивный алгоритм на основе деления Пом- маре, а также алгоритм на основе деления Жане реализованы на языке программирования C++ в виде отдельных утилит. Дальнейшие изучение и сравнение быстродействия этих утилит между собой и с другими программными пакетами позволили отказаться от некоторых шагов алгоритма и найти компромисс между производительностью и функциональностью. Итоговая версия алгоритма, использующего деление Пом- маре, реализована в виде пакета BIBasis, встроенного в системы компьютерной алгебры с открытым исходных кодом Macaulay2 и REDUCE. Пакет доступен под лицензией GPL v2.
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:
Международная конференция по компьютерной алгебре и дифференциальным уравнениям. Доклад «О вычислении базисов Грёбнера над F2», Финляндия, Турку, 20 — 23 февраля 2007 г.
11-ое международное совещание по компьютерной алгебре. Доклад «Ин- волютивный метод вычисления базисов Грёбнера над F2», Россия, Дубна, 24 — 25 мая 2007 г.
4-ое международное совещание «Квантовая физика и информация». Доклад «Алгоритмический подход к решению полиномиальных уравнений, описывающих квантовые схемы», Россия, Дубна, 15 — 19 октября 2007 г.
12-ое международное совещание по компьютерной алгебре. Доклад «О роли инволютивных критериев при вычислении булевых базисов Грёбнера», Россия, Дубна, 14 — 15 мая 2008 г.
Международная конференция «Математическое моделирование и вычислительная физика», MMCP 2009. Доклад «О вычислении булевых инволютивных базисов», Россия, Дубна, 7—11 июля 2009 г.
Международная конференция «Полиномиальная компьютерная алгебра», PCA 2010. Доклад «Булевы инволютивные базисы и решение задач
булевой выполнимости», Россия, Санкт-Петербург, 2 — 7 апреля 2010 г.
14-ое международное совещание по компьютерной алгебре. Доклад «Пакет BIBasis для вычисления булевых инволютивных базисов и базисов Грёбнера в системах компьютерной алгебры REDUCE и Macaulay2, Россия, Дубна, 2 — 3 июня 2011 г.
Публикации. По материалам диссертации опубликовано 8 печатных работ: 5 статей в рецензируемых журналах, рекомендованных ВАК [A1, A2, A3, A4, A5], и 3 статьи в сборниках трудов конференций [A6, A7, A8].
Личный вклад автора. Основные положения и выводы диссертации являются результатом самостоятельных исследований автора, выполненных под руководством д.ф.-м.н., профессора В.П. Гердта. Постановка и формализация задачи, разработка математических моделей и алгоритмов выполнены соискателем совместно с научным руководителем и соавторами. Практическая реализация, исследование форм представления данных, численные расчеты и анализ результатов проводились соискателем самостоятельно. Также соискателем самостоятельно создан и встроен в системы компьютерной алгебры REDUCE и Macaulay2 специализированный пакет для построения булевых базисов Грёбнера, и опубликована работа [A5], описывающая данный пакет.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Общий объем диссертации составляет 114 страниц, включая 34 рисунка и 4 таблицы. Список литературы содержит 63 наименования.
Похожие диссертации на Символьные алгоритмы и программы вычисления булевых базисов Грёбнера
-
