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

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

Зишш Михаил Владимирович

Символьные алгоритмы и программы вычисления булевых базисов Грёбнера

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 4 фев т

Москва - 2013

005049668

Работа выполнена в Лаборатории информационных технологий Объединенного института ядерных исследований.

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

профессор

Гердт Владимир Петрович

Официальные оппоненты: Абрамов Сергей Александрович

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

Вычислительный центр им. A.A. Дородницына РАН,

главный научный сотрудник

Зобиии Алексей Игоревич,

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

доцент,

МГУ имени М.В. Ломоносова

Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования Российский университет дружбы народов»

Защита состоится 1 марта 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при факультете вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова по адресу: 119991, г.Москва, ГСП-1, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня но тел. (495)939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Наука» - «Работа диссертационных советов» - «Д 501.001.44».

Автореферат разослан «AS » января 2013 г. Ученый секретарь

диссертационного совета Д 501.001.44 профессор

Н.П. Трифонов

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

Объект исследования и актуальность работы. Базис Грёбнера представляет собой каноническую форму системы алгебраических [1|, дифференциальных [2, 3| или разностных [4] многочленов многих переменных. Приведение систем таких многочленов к данной канонической форме является наиболее универсальным алгоритмическим подходом к их исследованию и решению.

Так, построение базиса Грёбнсра для системы алгебраических уравнений полиномиального типа позволяет установить её совместность (т.е. наличие общих корней у многочленов системы), определить число (а в случае бесконечного числа — размерность пространства) решений, привести исходную систему к треугольному виду, либо исключить часть переменных. В целом метод базисов Грёбнсра является обобщением метода Гаусса на случай нелинейных систем.

Алгоритмически задача нахождения базиса Грёбнсра для заданной системы многочленов в коммутативной алгебре была решена около полувека назад Б.Бухбергером [1], а соответствующий алгоритм [5| получил имя автора. С тех пор усилиями многих исследователей базисы Грёбнера нашли плодотворное применение в различных областях математики и естественных наук и в настоящее время обладают обширным числом практических приложений [6].

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

Напомним, что и—местной булевой функцией называется отображение

{0,1}" в {0,1} [8|. Для булевых функций определено понятие их суперпозиции, и, как следствие, для любого множества булевых функций может быть получено его замыкание — как множество всех функций, получаемых с помощью суперпозиции из функций исходного множества. В таком случае говорят, что множество <3 порождает замкнутый класс булевых функций Л: [<?] = Л (замкнутый, т.к. очевидно, что [[Л]] = [Я]). Если [Л] совпадает со множеством всех булевых функции, то порождающее множество <2 называют полным. Базисом замкнутого класса Л в теории булевых функций называют такое множество Скоторое порождает класс Л, но при этом ни одно несобственное подмножество <2 этого класса не порождает.

Известно, что множество булевых функций {1,х + у,ху} полно [8] (здесь 1 — функцня-констапта единица, х 4- у — сложение по .модулю 2, ху — конъюнкция). Причем функции х + у и ху являются соответственно сложением и умножением в поле ГалуаГ2 = {0,1}. Поэтому, пользуясь коммутативностью сложения и умножения, дистрибутивностью умножения относительно сложения и соотношениями ж + х = О, х ■ х = х, всякую функцию из замыкания множества {1,х + у, ху} (т.е. любую булеву функцию) можно представить в виде многочлена Жегалкина [8|:

где ак...г, е Рг- В данной работе мы будем называть многочлен Жегалкина булевым многочленом. Все такие многочлены от заданного конечного набора переменных {хь..., хг1} образуют кольцо, которое мы будем называть булевым. Это кольцо является эквивалентом булевой алгебры [9]. Более того, каждая булева функция представима булевым многочленом единственным образом [8]. Как и в случае булевых функций, множество булевых многочленов порождает идеал в булевом кольце, причем булево кольцо является кольцом главных идеалов, т.е. каждый идеал кольца порождается его единственным

элементом.

Базисы Грёбнера в целом, как уже было сказано, и булевы в частности, оказываются весьма полезными в случаях, когда решение некоторой задачи связано с исследованием и/или решением соответствующей полиномиальной системы |10-12|. В случае булева кольца наиболее распространенными задачами такого рода являются задачи криптоанализа и булевой выполнимости. Например, одним из первых ярких применений метода булевых базисов Грсб-нера стало решение сложной [ 13| проблемы — криптосистемы на скрытых отображениях нолей (Hidden Fields Equations) в криптографии с открытым ключом. Эта задача описывается системой квадратичных булевых многочленов от 80 переменных, и впервые ее решенне было получено именно путем вычисления булева базиса Грсбнсра с помощью алгоритма позднее — с помощью алгоритма F4 [14, 15].

Задача булевой выполнимости SAT (Boolean Satisfiability) — очень распространенная и, в общем случае, MV—полная [16] задача, которая возникает, в частности, при проверке корректности работы оборудования и программ, в робототехнике, при создании экспертных систем и т.п. Для решения этой задачи разработан ряд успешных и широко применяемых специализированных алгоритмов. В настоящее время уже известен ряд примеров [17] успешного применения техники булевых базисов Грёбнера к решению задачи булевой выполнимости. Через 12 лет после теоретического обоснования [18] применимости таких базисов для решения задач SAT был создан программный пакет PolyBoRi [19], использующий метод базисов Грёбнера и способный конкурировать с лучшими современными программами решения задач булевой выполнимости (SAT-solvers).

Приведем простой пример задачи булевой выполнимости, иллюстрирующий применение метода базисов Грёбнера для её решения, т.е. для ответа на вопрос: существует ли для заданной булевой функции такой набор значений

переменных, на котором функция принимает значение 1 (истина)? В терминах базисов Грёбнера данный вопрос формулируется следующим образом: состоит ли соответствующий базис Грсбнера из одного многочлена, который, в свою очередь, является единичным булевым мономом {1}) или нет? В последнем случае рассматриваемая задача является выполнимой.

Пусть булева функция, заданная в своей конъюнктивой нормальной форме, имеет вид:

/(х, у, г) = (а; V у V г) Л (х V у) Л (у V г) Л (2 V х) Л {х V у V г) /1 Л /2 А /3 Л /4 А /5

Приведем функцию к полиномиальному виду, используя следующие формулы:

х Л у —> ху, х\/ у —> ху + х + у, х —> 1 + 1

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

Д = хуг + ху + хг + уг + х + у + г + 1 /2 = ху + у < /з = 2/2 + 2 /4 = хг + х к = хуг

ч

Вычисление базиса Грсбнера для данной системы многочленов показывает, что этот базис равен {1}, т.е. полиномиальная система не имеет решений (несовместна), и задача невыполнима.

Ещё одним интересным применением булевых базисов Грёбнера может стать моделирование квантовых вычислений, т.е. построение унитарной матрицы квантовой цепи на классическом компьютере. Как показано в [20], для

квантовой цепи с помощью вентилей Тоффоли и Адамара (они образуют универсальный базис вентилей) сё цепная матрица однозначно определяется числом общих корней (когда все переменные принимают значения в Рг) системы булевых многочленов. В работе [21| описан пакет для системы Ма"Ы1ета1;1са [22], позволяющий пользователю по введенной квантовой цепи строить сё ценную унитарную матрицу стандартными методами линейной алгебры, а также автоматически создавать систему определяющих сё булевых многочленов. На практике, в силу ограниченности памяти компьютера, методами линейной алгебры удается промоделировать лишь 20-25 кубнтные схемы. И хотя задача построения базисов Грёбнера в булевых кольцах имеет экспоненциальную сложность [23], уже сейчас эта задача решается для некоторых систем многочленов от 100 и более переменных [17], что дает реальную надежду на то, что базисы Грёбнера, но крайне мерс в отдельных случаях, позволят сильно продвинуться в моделировании квантовых вычислений.

Стоит отметить, что случай полиномиальных систем с коэффициентами из конечного поля интересен не только тем, что имеет огромное количество практических приложений, но и простотой арифметики коэффициентов. Если рассматривать многочлены с коэффициентами из конечных полей большего размера или из поля рациональных чисел, то эффективность реализации операций с такими многочленами в значительной степени определяется эффективностью реализации операций над самими коэффициентами. Обеспечение же последней является отдельной и очень важной темой исследования [24].

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

и Fз французского математика Фожсра, целый ряд модификаций алгоритма

например, алгоритмы и СУ\У [25] — результат работы китайских и американских исследовагелей, а также инволютивный алгоритм [26, 27] Блинкова и Гердта. Булевой версии последнего и посвящена данная работа.

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

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

• Исследование современных алгоритмов построения базисов Грёбнера в полиномиальных кольцах и условий их применимости для вычисления булевых базисов Грёбнера.

• Разработка специализированного алгоритма, способного строить булев базис Грёбнера путем вычислений непосредственно в булевом кольце.

• Реализация разработанного алгоритма на языке С++ и ее оптимизация на основе эмпирических данных, полученных с помощью компьютерных экспериментов.

• Разработка программных пакетов, реализующих предложенный алгоритм в среде систем компьютерной алгебры с открытым исходным кодом.

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

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

• Впервые получена точная верхняя оценка на число элементов редуцированного булева базиса Грёбнера, что важно для оценки возможных затрат памяти на вычисление данного базиса.

• В системы компьютерной алгебры с открытым кодом REDUCE (версия 3.8) и Macaulay2 (версия 1.4.1) встроены новые пакеты, которые предназначены для построения булевых базисов Грёбнера и значительно превосходят по своей вычислительной эффективности имевшиеся в этих системах возможности для указанного построения.

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

Реализация алгоритма в виде пакета BIBasis встроена в открытые системы компьютерной алгебры Macaulay2 и REDUCE. Это существенно расширяет применимость указанных систем для решения задач, сводящихся к булевой логике. При этом Macaulay2 является одной из наиболее широко используемых программных систем специального назначения, ориентированных на задачи вычислительной коммутативной алгебры и алгебраической геометрии,

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

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

1. Проведено исследование применимости инволютивного алгоритма к задаче построения базисов Грёбнера и базисов Жане в булевом кольце. В результате показано, что инволютпвный алгоритм на основе деления Жане, равно как и алгоритм Бухбергера, может быть использован для этой цели только в том случае, когда исходное множество булевых многочленов дополняется множеством всех полевых биномов. После этого вычисление базиса Грёбнера производится в кольце многочленов над полем F2, а искомый булев базис является мультилинейным подмножеством найденного базиса Грёбнера.

2. Разработана версия инволютивного алгоритма на основе деления Пом-маре для построения редуцированных булевых базисов Грёбнера и базисов Поммарс непосредственно в булевом кольце, т.е. без использования полевых мономов. Доказаны корректность и завершаемость данного алгоритма. Показано, что он позволяет эффективно использовать представление булевых многочленов в памяти ЭВМ и простоту их арифметики. Получена точная верхняя оценка на число элементов редуцированного булева базиса Грёбнера.

3. Разработанный булев инволютпвный алгоритм на основе деления Пом-маре, а также алгоритм на основе деления Жане реализованы на языке программирования С-т в виде отдельных утилит. Дальнейшие изучение и сравнение быстродействия этих утилит между собой и с другими программными пакетами позволили отказаться от некоторых шагов ал-

горитма и найти компромисс между производительностью и функциональностью. Итоговая версия алгоритма, использующего деление Пом-маре, реализована в виде пакета BIBasis, встроенного в системы компьютерной алгебры с открытым исходных кодом Macaulay2 и REDUCE. Пакет доступен под лицензией GPL v2.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

• Международная конференция по компьютерной алгебре и дифференциальным уравнениям. Доклад «О вычислении базисов Грёбнера над F2», Финляндия, Турку, 20 - 23 февраля 2007 г.

• 11-ое международное совещание по компьютерной алгебре. Доклад «Ин-волютивный метод вычисления базисов Грёбнера над F2», Россия, Дубна, 24 — 25 мая 2007 г.

• 4-ое международное совещание «Квантовая физика и информация». Доклад «Алгоритмический подход к решению полиномиальных уравнений, описывающих квантовые схемы», Россия, Дубна, 15 — 19 октября 2007 г.

• 12-ое международное совещание по компьютерной алгебре. Доклад «О роли инволютивных критериев при вычислении булевых базисов Грёбнера», Россия, Дубна, 14 — 15 мая 2008 г.

• Международная конференция «Математическое моделирование и вычислительная физика», ММСР 2009. Доклад «О вычислении булевых инволютивных базисов», Россия, Дубна, 7—11 июля 2009 г.

• Международная конференция «Полиномиальная компьютерная алгебра», РСА 2010. Доклад «Булевы инволютивные базисы и решение задач

булевой выполнимости», Россия, Санкт-Петербург, 2 — 7 апреля 2010 г.

• 14-ое международное совещание по компьютерной алгебре. Доклад «Пакет BIBasis для вычисления булевых инволютивных базисов и базисов Грёбнера в системах компьютерной алгебры REDUCE и Масаи1ау2», Россия, Дубна, 2 — 3 июня 2011 г.

Публикации. По материалам диссертации опубликовано 8 печатных работ: 5 статей в рецензируемых журналах, рекомендованных ВАК [Al, А2, A3, А4, А5], и 3 статьи в сборниках трудов конференций [А6, А7, А8].

Личный вклад автора. Основные положения и выводы диссертации являются результатом самостоятельных исследований автора, выполненных под руководством д.ф.-м.н., профессора В.П. Гердта. Постановка и формализация задачи, разработка математических моделей и алгоритмов выполнены соискателем совместно с научным руководителем и соавторами. Практическая реализация, исследование форм представления данных, численные расчеты и анализ результатов проводились соискателем самостоятельно. Также соискателем самостоятельно создан и встроен в системы компьютерной алгебры REDUCE и Macaulay2 специализированный пакег для построения булевых базисов Грёбнера, и опубликована работа [А5], описывающая данный пакет.

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

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

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

12

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

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

Рг = {0,1} — поле Галуа характеристики 2;

X = {хь-.. ,жп} — множество независимых переменных;

— кольцо многочленов от переменных X над полем ¥2;

В [А'] — кольцо булевых многочленов от переменных X;

Мд[Х] — множество всех булевых мономов от переменных X;

(Р) — идеал, порожденный конечным множеством многочленов F;

ск^(ы) — степень переменной в мономе ы;

= ск^(ы) — полная степень монома и;

>--мономиальное упорядочение, такое, что Х\ >- Х2 >- • ■ ■ >- хп >- 1;

1т(/) — старший моном многочлена /;

Булево кольцо В [X] определяется как кольцо многочленов Жегалки-на [8], которое является коммутативным факторкольцом

В[АГ] :=Г2[Х] /(х2 + хи...,х2п + хп).

Легко видеть, что умножение в булевом кольце идемпотентпо, а сложение — нильпотентно:

V р е В [X] : р2 = р, р + р = 0.

Здесь же вводится определение частного от деления булевых мономов: Определение 1.3.5. Булев моном т 6 Мд[А'] будем называть частным от деления монома Ь на моном а в булевом кольце В [X], если тп ■ а = Ь и ск^(т) = тт{<к^(т,-) | тща = Ь}.

Доказано следующее Утверждение 1.3.1. Частное от деления булевых мономов единственно.

Далее вводится понятие базиса Грсбнера и нормальной формы многочлена / по модулю заданного конечного полиномиального множества F: Определение 1.3.7. Пусть даны идеал I С В [X] и упорядочение X. Конечное подмножество С С X называется базисом Грёбпера идеала Т (относительно упорядочения >-), если

V/ 6 1 3 £ € (3 такой, что 1т(д) | 1т(/).

Нормальная форма / по модулю ^ определяется как остаток от деления / на элементы из Г.

Далее в первой главе приводятся основные, необходимые для понимания работы инволютивного алгоритма в дальнейшем, определения из теории ин-волютивных базисов, восходящей к работе [28] и основанной на теории инво-лютивных делений [26]. Полностью все эти определения даются в работе [27|.

Приведём пример одного из инволютивных делений - деления Помма-ре [26), на основе которого получен главный алгоритмический результат диссертации.

Определение 1.4.10. Для монома и = х'[' ■ ■ ■ х'^х'^, где (1к > 0 переменные X], 3 ^ к называются мультипликативными (по Поммаре), все остальные, соответственно, — немультиплипкативными. Для и = 1 все переменные считаются мультипликативными. Моном и является инволютивным делителем Поммаре монома V (обозначение и ¡р и) если V = и ■ ш и все переменные положительной степени в мономе и) являются мультипликативными для этого монома.

Также в первой главе описываются особенности булева кольца, не позволяющие использовать существующие алгоритмы построения базисов Грёб-нера непосредственно в этом кольце. Этими особенностями являются: (1) на-

14

рушение свойства совместимости мономиального упорядочения с операцией умножения в булевом кольце; (2) минимальный базис Грсбнера идеала, не обязательно совпадаем с порождающим его многочленом. Напомним, что булево кольцо является кольцом главных идеалов. Мы иллюстрируем указанные особенности простыми примерами:

XI >- Х2 Х' > XI ■ XI >- XI ■ Х2 ->• XI -< Х\ ■ Х2

и

ХЬ Х2 € (хх Х2 + Х\ + х2) СВ[хьх2].

Основные результаты первой главы опубликованы в [А6, А1| и состоят в следующем:

• Для булева кольца определены: деление мономов, нормальная форма многочлена ио модулю заданного конечного множества многочленов, базис Грсбнера.

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

Во второй главе рассматриваются теоретические аспекты вычисления булевых базисов Грсбнера.

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

Поскольку, как уже было выяснено в первой главе, ни один из существующих алгоритмов не может работать непосредственно в булевом кольце, в данном разделе описана возможность построения булева базиса Грёбнера с помощью вычислений в кольце F2[A'j. Для этого исходный набор булевых многочленов {/i,...,/m} дополняется множеством всех полевых биномов и для полученного набора {/[,..., f'm, Ф} (где Д е F2[X] — прообраз /,• относительно гомоморфизма факторизации F2[X] В[Х]), вычисляется базис Грёбнера в кольце F2[X]. Полученный базис имеет вид {д[,... ,д'к, Ф'}, где д[ 6 F2[X], д[ ф Ф, Ф' С Ф, причем многочлены д\ не содержат переменных в степени выше 1.

Утверждение 2.2.1. Набор булевых многочленов {(/ь - ■ .,д'к) является искомым базисом Грёбнера идеала (/ь ..., /ш).

Доказательство этого утверждения можно найти в [б].

Очевидным недостатком этого способа вычислений является увеличение числа многочленов в исходном базисе, что влечёт за собой рост времени работы используемого алгоритма.

Во втором разделе главы подробно описаны инволютивный алгоритм на основе деления Жане [26, 27] и его ключевые подалгоритмы, работающие в кольце F2[X]. Сами алгоритмы представлены в виде псевдокода, исходный же код утилиты на языке программирования С— доступен по адресу в Интернете http: //ЬрЪ. googlecode. com. Реализация этого алгоритма используется для сравнения с новой разработкой — ииволютивньim алгоритмом на основе деления Поммаре (описан ниже) и для иллюстрации недостатков работы в кольце F2[X].

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

нис только на мультипликативные переменные.

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

Утверждение 2.3.1. Разделение неременных монома на мультипликативные и немультипликативные по Поммарс и, следовательно, свойство делимости но Поммарс сохраняются гомоморфизмом кольца в кольцо В [X].

Представлена разработанная версия инволютивного алгоритма на основе деления Поммарс.

Algorithm 1 PommarctBasis(F, у)

Вход: F С \ {0}, >--мопомиальное упорядочение;

Выход: Р С ¥2[Х] — базис Поммаре идеала (F); 1: выбрать / 6 F с наименьшим 1т(/) относительно >-2: Р : {/}

3: Q ~ F\{f}u U ■ х \ X е NMv(f)} 4: while Q ф 0 do

5: h := О

6: while <3/0 AND /t = 0 do

7: выбрать q E Q с наименьшим lm(g) относительно >-

8: Q Q\ {?}

9: h := HeadNormalForm-p(q, P)

10: Od

li: if h ф 0 then

12: for all {p € P I lm(/i) \v lm(p)} do

13: P:=P\{p}

14: Q:=QU{p}\{p-x\x€NMv(p)}

15: Od

16: P~PU{h}

17: Q := Qu{h-X I x € NMP{h)}

18: fi

19: Od

20: P := AutoreduceTailsp(P.)

21: return P

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

Доказаны следующие теоремы: Теорема 2.3.1. Алгоритм Роттаге1Вая1я корректен и завершается за конечное число шагов для любого набора многочленов ВиФС [А"]. Следствие 2.3.1. Базис Поммаре, получаемый в результате работы алгоритма PommaretBasis, примененного к набору В и Ф, может содержать только булевы многочлены н произведения полевых многочленов на немультиплнка-тивные переменные их старших мономов.

Следствие 2.3.2. Мощность базиса Поммаре идеала в Гг[Х], порожденного набором булевых многочленов от п переменных и дополненного множеством Ф полевых многочленов, ограничена 2" — 1.

Теорема 2.3.2. Для данного набора В булевых многочленов идеал (В) в булевом кольце В [X] имеет единственный базис Грёбнера. Теорема 2.3.3. Алгоритм PommaretBasis корректен и завершается за конечное число шагов для любого набора многочленов ^сВ [X]. Теорема 2.3.3. Мощность приведенного базиса Грёбнера С в булевом кольце В [X] ограничена

И в заключительной части третьего раздела подробно описываются инволютивный алгоритм на основе деления Поммаре и его основные подалго-ритмы в том виде, в каком они были реализованы в утилите ВРВ. Как и в предыдущем разделе, алгоритмы представлены в виде псевдокода, а исходный код можно найти но тому же адресу http://bpb.googlecode.com.

Основные результаты второй главы опубликованы в [А1, А8, А2| и состоят в следующем:

• Показана применимость инволютивного алгоритма, выполняющего вычисления в коммутативной алгебре, для построения булевых базисов Грёбнера путем проведения вычислений в кольце Р2[АГ] и дополнения исходной системы булевых многочленов нолевыми биномами.

• Разработана версия инволютивного алгоритма, применимого к построению булевых базисов Грёбнера непосредственно в булевом кольце и основанного на делении Поммарс. Доказаны корректность и завершае-мость данного алгоритма.

• Получена точная верхняя оценка на число элементов редуцированного булева базиса Грёбнера.

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

В первом разделе рассматриваются способы представления монома в памяти ЭВМ, и обосновывается выбор односвязных списков для хранения мономов в реализациях алгоритмов Жане (т.е. для работы в кольце и Поммаре (для работы в В [А']). В реализации алгоритма Поммаре список хранит только номера переменных, входящих в моном в степени 1, а в реализации алгоритма Жане — и номера, и показатели степеней переменных, входящих в моном в положительной степени. Приводятся оценки вычислительной сложности для основных операций над мономами в таком представлении.

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

рассматривается в работе [А4]). На конкретном примере иллюстрируется реализация основных для рассматриваемых алгоритмов операций над многочленами: сложение двух многочленов и умножение многочлена на неременную. Приводится оценка сложности для каждой их этих операций.

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

Во втором и третьем разделах главы описывается пакет BIBasis, реализующий инволютивный алгоритм на основе деления Поммаре, для открытых систем компьютерной алгебры Macaulay2 и REDUCE. Macaulay2 — это система, специализированная для вычислений в аналитической геометрии и коммутативной алгебры. Её ядро и основные алгоритмы написаны на языке программирования С——. Пакет BIBasis в этой системе также реализован на языке С—к REDUCE — система общего назначения, написана на Standard LISP — диалекте языка LISP. На этом же языке написан и пакет BIBasis для системы REDUCE.

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

Для каждой упомянутой системы приводятся примеры использования пакета BIBasis, иллюстрирующие его возможности. Пример использования BIBasis в системе REDUCE:

1: loacLpackage bibasis; 2: variables := {x0,xl,x2,x3,x4}$ 3: polynomials := {x0*x3+xl*x2,x2*x4+x0}$ 4: bibasis (polynomials, vELriables, deglex, t) ; {xl*x2*(x3 +1), xl*(xO + x2), x0*(x2 + 1), x0*x3 + xl*x2, x0*(x4 + 1), x2*x4 + x0>

Основные результаты третьей главы опубликованы в [А4, А5] и состоят в следующем:

• Обоснован выбор внутреннего представления данных: мономы и многочлены — односвязные упорядоченные списки.

• Инволютивнын алгоритм, основанный на делении Поммаре, реализован на языке С++ в виде отдельной программы, на языке С f v — в виде пакета BIBasis для системы Macaulay2, и на языке Standard LISP — в виде пакета BIBasis для системы REDUCE.

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

В этой главе выбираются тестовые серии примеров из набора стандартных бенчмарков [29, 30| и из коллекции SAT-02 Challenge Set [31). Используются серии cyclic, eco, redcyc(lic), redeco, ezfact, xor-chains и серия life, полученная из анализа [32) известной игры «Жизнь» Дж. Конуэя.

21

Далее в главе приводятся результаты сравнения времен счета выбранных примеров. Сравниваются утилиты BJB и ВРВ, реализующие булевы инво-лютивные алгоритмы Жане и Поммаре соответственно, утилита ВРВ сравнивается с библиотекой PolyBoRi [19] и системой компьютерной алгебры Singular [33|, пакет BIBasis в системе Macaulay2 — со стандартным алгоритмом gb из этой системы, и пакет BIBasis в системе REDUCE сравнивается с пакетом Groebner. Результаты сравнений представлены в виде графиков, два из которых приводятся ниже.

Рис. 1. Зависимость времени работы системы Macaulay2 от числа переменных для серии eco.

Рис. 2. Зависимость времени работы системы REDOCE от числа переменных для серии eco.

Два представленных графика отображают типичный результат сравнения быстродействии пакета BIBasis и стандартных пакетов в системах Macaulay2 и REDUCE соответственно.

В заключительной части главы анализируются результаты проведенных сравнений, и делаются следующие выводы об эффективности булева инволю-тивного алгоритма, основанного на делении Поммаре:

• на большинстве тестовых примеров ВРВ быстрее Singular;

• существуют SAT примеры, на которых ВРВ быстрее PolyBoRi;

• на подавляющем большинстве тестовых примеров BIBasis быстрее gb и Groebner;

• производительность процессора важнее объема оперативной памяти;

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

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

Список публикаций

А1. Гердт В. П., Зинин М. В. Инволютивный метод вычисления базисов Грёб-нера над F2 // Программирование. 2008. Т. 34, № 4. С. 191-203.

А2. Гердт В. П., Зинин М. В. О роли инволютивных критериев при вычислении булевых базисов Грсбнсра // Программирование. 2009. Т. 35, № 2. С. 90-97.

A3. Gerdt V. P., Zinin M. V. An algorithmic approach to solving polynomial equations associated with quantum circuits // Physics of Particles and Nuclei Letters. 2009. Vol. 6, no. 7. Pp. 521-525.

A4. Гердт В. П., Зпнин М. В., Блинков Ю. А. О вычислении булевых инво-лютивных базисов // Программирование. 2010. Т. 36, № 2. С. 117-125.

А5. Зинин М. В. Пакет BiBasis для вычисления булевых инволютивных базисов и базисов Грёбнера в системах компьютерной алгебры REDUCE и Macaulау2 ,/,/ Программирование. 2012. Т. 38, № 2. С. 55-67.

А6. Gerdt V. Р., Zinin М. V. Gröbner bases over F2 /'/ Computer Algebra and Differential Equations. Vol. 67. 2007. Pp. 59-68.

A7. Gerdt V., Zinin M., Blinkov Y. On computation of Boolean involutive bases // Proceedings of International Conference Polynomial Computer Algebra. 2009. Pp. 17-24.

A8. Gerdt V. P., Zinin M. V. A Pommaret Division Algorithm for Computing Gröbner Bases in Boolean Rings // Proceedings of ISSAC 2008. ISSAC'08. New York: ACM Press, 2008. Pp. 95-102.

Цитированная литература

1. Buchberger В. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal): Ph.D. thesis / Mathematical Institute, University of Innsbruck, Austria. 1965.

2. Kandri-Rody A., Weispfenning V. Non-commutative Gröbner bases in alge-

bras of solvable type // Journal of Symbolic Computation. 1990. Vol. 9. Pp. 1-26.

3. Carra'Ferro G. Gröbner bases and differential algebra // Proceedings of the 5tli international conference, AAECC-5 on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes / Ed. by L. Huguet, A. Poli. Springer-Verlag New York, Inc. New York, NY, USA, 1987. Pp. 129 - 140.

4. Gerdt V. P. Oil Computation of Gröbner Bases for Linear Difference Systems. // Nuclear Instruments and Methods in Physics Research. 2006. Vol. 559(1). Pp. 211 -214. URL: arXiv.org:math-ph/0509050.

5. Buchberger B. Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory // Multidimensional Systems Theory - Progress, Directions and Open Problems in Multidimensional Systems. Copyright: Reidel Publishing Company, Dordrecht - Boston - Lancaster, The Netherlands, 1985. Pp. 184-232.

6. Brickenstcin M. Boolean Gröbner bases — Theory, Algorithms and Applications: Ph. D. thesis / Technischen Universität Kaiserslautern. 2010.

7. Sakai К., Sato Y. Boolean Gröbner Bases, 1988.

8. Марченков . . Замкнутые классы булевых функций. Москва: Физматлит, 2000. ISBN: 5-9221-0066-1.

9. Hsiang J., Huang G. Some Fundamental Properties of Boolean Ring Normal Forms // DIMACS series on Discrete Mathematics and Computer Science: The Satisfiability Problem. 1997. Vol. 35. Pp. 587-602.

10. Sato Y., Inouc S., Suzuki A. et al. Boolean Gröbner bases //J. Symb. Comput. 2011. Vol. 46, no. 5. Pp. 622-632.

11. Kalorkoti K. Model checking in the modal ¿¿-calculus arid generic solutions // J. Symb. Comput. 2011. Vol. 46, no. 5. Pp. 584-594.

12. Bernaseoni A., Codenotti B., Crespi V., Resta G. Computing Grobner Bases in the Boolean Setting with Applications to Counting.

13. Bardet. M., Faugere J.-C., Salvy B., Spaenlehauer P.-J. On the Complexity of Solving Quadratic Boolean Systems. 2011. URL: arXiv.org: 1112.6263vl.

14. Faugere J.-C. A new efficient algorithm for computing Grobner bases (F4) // Journal of Pure and Applied Algebra. 1999. Vol. 139, no. 1-3. Pp. 61-88. URL: http://www-salsa.Iip6.fr/~jcf/Papers/F99a.pdf.

15. Faugere J.-C. A new efficient algorithm for computing Grobner bases without reduction to zero (F3) // Proceedings of the 2002 international symposium on Symbolic and algebraic computation. ISSAC '02. New York, NY, USA: ACM, 2002. Pp. 75-83. URL: http://www-salsa.lip6.fr/~jcf/Papers/ F02a.pdf.

16. Garey M. R., Johnson D. S. Computers and Intractability: a Guide to the Theory of Af'P-completeness. New York: Freeman, 1978.

17. Brickenstein M., Dreyer A., Greuel G. et al. New developments in the theory of Grobner bases and applications to formal verification // Journal of Pure and Applied Algebra, Special issue on Theoretical Effectivity and Practical Effectivity of Grobner Bases. 2009. Vol. 213, no. 8. Pp. 1612—1635.

18. Clegg M., Edmonds J., Impagliazzo R. Using the Grobner Basis algorithm to find proofs of unsatisfiability // Proc. 28th Annual ACM Symposium on Theory of Computing. 1996. Pp. 174-183.

19. Brickenstein M., Dreyer A. PolyBoRi: A framework for Grobner-basis computations with Boolean polynomials // Journal of Symbolic Computation. 2009. Vol. 44, no. 9. Pp. 1326 - 1345. Effective Methods in Algebraic Geometry. URL: http://dx.doi.org/10.1016/j.jsc.2008.02.017.

20. Dawson C. M., Hasclgrove H. L., Hines A. P. et al. Quantum computing and polynomial equations over the finite field // Quantum Information and Computation. 2005. Vol. 5, no. 2. Pp. 102-112. URL: arXiv.org: quant-ph/0408129vl.

21. Gerdt V. P., Kraglcr R., Prokopenya A. N. Computer Algebra Application to Simulation of Quantum Computation // Proceedings of the DST-U-NISA-JINR symposium, Ed. by S. Sofianos. Models and Methods in Few-and Many-Body Systems. University of South Africa, Pretoria, 2007. Pp. 219-232.

22. Mathematica 6.0. Champaign, Illinois, USA: Wolfram Research, Inc., 2007. URL: http://www.wolfram.com/.

23. Bardet M., Faugere J. C., Salvy B. On the complexity of Grobtier basis computation of semi-regular overdetermined algebraic equations // International Conference on Polynomial System Solving - ICPSS. 2004. Pp. 71-75. URL: http://www-salsa.Iip6.fr/~jcf/Papers/43BF.pdf.

24. Arithmetic of Finite Fields. Vol. 5130 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2008.

25. Volny IV F. New Algorithms for Computing Grobner Bases: Ph. D. thesis / Clemson University. 2011. URL: http://etd.lib.clemson.edu/ documents/1306872881/Volny_clemson_0050D_11180.pdf.

26. Gerdt V. P., Blinkov Y. A. Involutive Bases of Polynomial Ideals // Math-

omatics and Computers in Simulation. 1998. Vol. 45. Pp. 519-542. URL: arXiv.org:math.AC/9912027.

27. Gerdt V. P. Involutive Algorithms for Computing Grobner Bases /,/ Computational Commutative and Non-Commutative Algebraic Geometry, Ed. by S. Cojocaru, G. Pfistcr, V. Ufnarovski. NATO Science Scries. NATO Science Series, IOS Press, 2005. Pp. 199-225. URL: arXiv.org:math.AC/0501 111.

28. Жарков . ., Блинков . . Инволютивные системы алгебраических уравнений // Программирование. 1994. Pp. 53-56.

29. Bini D., Mourrain В. Polynomial test suite. 2006. URL: http://www-sop. inria.fr/saga/POL.

30. VerscheldeJ. The database of polynomial systems. 2011. URL: http://www. math.uic.edu/~jan/demo.html.

31. Hoos H. H., Stiitzle T. SATLIB: An Online Resource for Research on SAT // SAT 2000, Ed. by I. P. Gent, H. V. Maaren, T. Walsh. IOS Press, 2000. 283 - 292 pp.

32. Kornyak V. V. On Compatibility of Discrete Relations // CASC-2005 proceedings. LNCS 3718. Springer-Verlag, 2005. 272-284 pp. URL: arXiv.org: math-ph/0504048.

33. Decker W., Grcuel G.-M., Pfister G., Schonemann H. Singular 3-1-3 - A computer algebra system for polynomial computations. 2011. URL: http: //www. singular. uni-kl. de.

Введение

Глава 1. Булевы базисы Грёбнера и инволютивные базисы

1.1. Основные обозначения

1.2. Булевы функции, многочлены и кольцо.

1.3. Булевы базисы Грёбнера.

1.4. Булевы инволютивные базисы.

Глава 2. Алгоритмы вычисления булевых базисов.

2.1. Некоторые существующие алгоритмы построения базисов Грёбнера

2.1.1. Алгоритм Бухбергера

2.1.2. Инволютивный алгоритм.

2.1.3. Вычисление булевых базисов в кольце

2.2. Инволютивный алгоритм на основе деления Жане.

2.2.1. Подробное описание алгоритма.

2.3. Инволютивный алгоритм на основе деления Поммаре

2.3.1. Вычисление базиса Поммаре в кольце ¥2[Х].

2.3.2. Вычисление базиса Поммаре в кольце В [X].

2.3.3. Подробное описание алгоритма.

Глава 3. Программная реализация.

3.1. Реализация утилит ВЛВ и ВРВ на языке программирования

Си++.

3.1.1. Преимущества и недостатки векторизации в представлении мономов

3.1.2. Представление мономов односвязным списком

3.1.3. Представление многочленов.

3.1.4. Выбор мономиального упорядочения.

3.2. Реализация пакета BIBasis в системе Macaulay

3.2.1. Реализация и представление данных.

3.2.2. Пользовательский интерфейс.

3.2.3. Примеры использования.

3.3. Реализация пакета BIBasis в системе REDUCE.

3.3.1. Реализация и представление данных.

3.3.2. Пользовательский интерфейс.

3.3.3. Примеры использования.

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

4.1. Выбор тестовых примеров.

4.2. Сравнение делений Жане и Поммаре.

4.3. Сравнение с пакетами Singular и PolyBoRi.

4.4. Система компьютерной алгебры Macaulay2, сравнение пакета BIBasis и встроенного пакета gb.

4.5. Система компьютерной алгебры REDUCE, сравнение пакетов BIBasis и Groebner.

4.6. Выводы.

Объект исследования и актуальность работы. Базис Грёбне-ра представляет собой каноническую форму системы алгебраических [1], дифференциальных [2, 3] или разностных [4] многочленов многих переменных. Приведение систем таких многочленов к данной канонической форме является наиболее универсальным алгоритмическим подходом к их исследованию и решению.

Так, построение базиса Грёбнера для системы алгебраических уравнений полиномиального типа позволяет установить её совместность (т.е. наличие общих корней у многочленов системы), определить число (а в случае бесконечного числа — размерность пространства) решений, привести исходную систему к треугольному виду, либо исключить часть переменных. В целом метод базисов Грёбнера является обобщением метода Гаусса на случай нелинейных систем.

Алгоритмически задача нахождения базиса Грёбнера для заданной системы многочленов в коммутативной алгебре была решена около полувека назад Б.Бухбергером [1], а соответствующий алгоритм [5] получил имя автора. С тех пор усилиями многих исследователей базисы Грёбнера нашли плодотворное применение в различных областях математики и естественных наук и в настоящее время обладают обширным числом практических приложений [6].

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

Напомним, что п—местной булевой функцией называется отображение 0,1}п в { 0,1} [8]. Для булевых функций определено понятие их суперпозиции, и, как следствие, для любого множества булевых функций может быть получено его замыкание — как множество всех функций, получаемых с помощью суперпозиции из функций исходного множества. В таком случае говорят, что множество ф порождает замкнутый класс булевых функций Я: [ф] = Я (замкнутый, т.к. очевидно, что [[Я]} = [Л]). Если [Я] совпадает со множеством всех булевых функций, то порождающее множество ф называют полным. Базисом замкнутого класса Я в теории булевых функций называют такое множество Скоторое порождает класс Я, но при этом ни одно несобственное подмножество ф этого класса не порождает.

Известно, что множество булевых функций {1,х + у,ху} полно [8] (здесь 1 — функция-константа единица, х + у — сложение по модулю 2, ху — конъюнкция). Причем функции х + у и ху являются соответственно сложением и умножением в поле Галуа ¥2 = {0,1}. Поэтому, пользуясь коммутативностью сложения и умножения, дистрибутивностью умножения относительно сложения и соотношениями ж+я = О, х-х = х, всякую функцию из замыкания множества {1,х + у, ху} (т.е. любую булеву функцию) можно представить в виде многочлена Жегалкина [8]: где а, £ В данной работе мы будем называть многочлен Жегалкина булевым многочленом. Все такие многочлены от заданного конечного набора переменных {х\,.,хп} образуют кольцо, которое мы будем называть булевым. Это кольцо является эквивалентом булевой алгебры [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}) или нет? В последнем случае рассматриваемая задача является выполнимой.

Пусть булева функция, заданная в своей конъюнктивой нормальной форме, имеет вид: ж, у, £) = {х V у V г) Л (х V у) Л (у V г) Л (г V х) Л (х V у V г) 11 А к А /з Л /4 Л /б

Приведем функцию к полиномиальному виду, используя следующие формулы: х Л у —> ху, х V у —> ху + х + у, х —> х + 1

Тогда булева выполнимость рассматриваемой задачи сводится к существованию решения в F2 у системы булевых многочленов / х = хуг + ху + хг + уг + х + у + г + 1 /2 = ху + у < /з = 2/2 + г ¡¿ = хг + х к = ХУ*

Вычисление базиса Грёбнера для данной системы многочленов показывает, что этот базис равен {1}, т.е. полиномиальная система не имеет решений (несовместна), и задача невыполнима.

Ещё одним интересным применением булевых базисов Грёбнера может стать моделирование квантовых вычислений, т.е. построение унитарной матрицы квантовой цепи на классическом компьютере. Как показано в [20], для квантовой цепи с помощью вентилей Тоффоли и Адамара (они образуют универсальный базис вентилей) её цепная матрица однозначно определяется числом общих корней (когда все переменные принимают значения в Рг) системы булевых многочленов. В работе [21] описан пакет для системы Ма-^ета-Ыса [22], позволяющий пользователю по введенной квантовой цепи строить её цепную унитарную матрицу стандартными методами линейной алгебры, а также автоматически создавать систему определяющих её булевых многочленов. На практике, в силу ограниченности памяти компьютера, методами линейной алгебры удается промоделировать лишь 20-25 кубитные схемы. И хотя задача построения базисов Грёбнера в булевых кольцах имеет экспоненциальную сложность [23], уже сейчас эта задача решается для некоторых систем многочленов от 100 и более переменных [17], что дает реальную надежду на то, что базисы Грёбнера, по крайне мере в отдельных случаях, позволят сильно продвинуться в моделировании квантовых вычислений.

Стоит отметить, что случай полиномиальных систем с коэффициентами из конечного поля F2 интересен не только тем, что имеет огромное количество практических приложений, но и простотой арифметики коэффициентов. Если рассматривать многочлены с коэффициентами из конечных полей большего размера или из поля рациональных чисел, то эффективность реализации операций с такими многочленами в значительной степени определяется эффективностью реализации операций над самими коэффициентами. Обеспечение же последней является отдельной и очень важной темой исследования [24].

Таким образом, можно утверждать, что в настоящее время существует практическая потребность в быстрых и высокоэффективных алгоритмах для вычисления булевых базисов Грёбнера и их реализациях, что заставляет исследователей искать и находить новые, более эффективные алгоритмы для их построения. К таковым можно отнести уже упоминавшиеся алгоритмы F4 и ^ французского математика Фожера, целый ряд модификаций алгоритма например, алгоритмы С2У и СУ\¥ [25] — результат работы китайских и американских исследователей, а также инволютивный алгоритм [26, 27] Блинкова и Гердта. Булевой версии последнего и посвящена данная работа.

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

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

• Исследование современных алгоритмов построения базисов Грёбнера в полиномиальных кольцах и условий их применимости для вычисления булевых базисов Грёбнера.

• Разработка специализированного алгоритма, способного строить булев базис Грёбнера путем вычислений непосредственно в булевом кольце.

• Реализация разработанного алгоритма на языке С++ и ее оптимизация на основе эмпирических данных, полученных с помощью компьютерных экспериментов.

• Разработка программных пакетов, реализующих предложенный алгоритм в среде систем компьютерной алгебры с открытым исходным кодом.

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

• Разработан новый эффективный алгоритм построения базиса Грёбне-ра для системы булевых многочленов, который, в отличие от других известных алгоритмов, позволяет проводить вычисления непосредственно в булевом кольце. Доказана завершаемость данного алгоритма за конечное число шагов.

• Впервые получена точная верхняя оценка на число элементов редуцированного булева базиса Грёбнера, что важно для оценки возможных затрат памяти на вычисление данного базиса.

• В системы компьютерной алгебры с открытым кодом REDUCE (версия 3.8) и Macaulay2 (версия 1.4.1) встроены новые пакеты, которые предназначены для построения булевых базисов Грёбнера и значительно превосходят по своей вычислительной эффективности имевшиеся в этих системах возможности для указанного построения.

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

Реализация алгоритма в виде пакета BIBasis встроена в открытые системы компьютерной алгебры Macaulay2 и REDUCE. Это существенно расширяет применимость указанных систем для решения задач, сводящихся к булевой логике. При этом Macaulay2 является одной из наиболее широко используемых программных систем специального назначения, ориентированных на задачи вычислительной коммутативной алгебры и алгебраической геометрии, a REDUCE является системой компьютерной алгебры общематематического назначения и находит применение в различных областях науки и техники.

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

1. Проведено исследование применимости инволютивного алгоритма к задаче построения базисов Грёбнера и базисов Жане в булевом кольце. В результате показано, что инволютивный алгоритм на основе деления Жане, равно как и алгоритм Бухбергера, может быть использован для этой цели только в том случае, когда исходное множество булевых многочленов дополняется множеством всех полевых биномов. После этого вычисление базиса Грёбнера производится в кольце многочленов над полем F2, а искомый булев базис является мультилинейным подмножеством найденного базиса Грёбнера.

2. Разработана версия инволютивного алгоритма на основе деления Пом-маре для построения редуцированных булевых базисов Грёбнера и базисов Поммаре непосредственно в булевом кольце, т.е. без использования полевых мономов. Доказаны корректность и завершаемость данного алгоритма. Показано, что он позволяет эффективно использовать представление булевых многочленов в памяти ЭВМ и простоту их арифметики. Получена точная верхняя оценка на число элементов редуцированного булева базиса Грёбнера.

3. Разработанный булев инволютивный алгоритм на основе деления Поммаре, а также алгоритм на основе деления Жане реализованы на языке программирования С++ в виде отдельных утилит. Дальнейшие изучение и сравнение быстродействия этих утилит между собой и с другими программными пакетами позволили отказаться от некоторых шагов алгоритма и найти компромисс между производительностью и функциональностью. Итоговая версия алгоритма, использующего деление Поммаре, реализована в виде пакета BIBasis, встроенного в системы компьютерной алгебры с открытым исходных кодом Macaulay2 и REDUCE. Пакет доступен под лицензией GPL v2.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

• Международная конференция по компьютерной алгебре и дифференциальным уравнениям. Доклад «О вычислении базисов Грёбнера над i<2», Финляндия, Турку, 20 — 23 февраля 2007 г.

• 11-ое международное совещание по компьютерной алгебре. Доклад «Инволютивный метод вычисления базисов Грёбнера над F2», Россия, Дубна, 24 - 25 мая 2007 г.

• 4-ое международное совещание «Квантовая физика и информация». Доклад «Алгоритмический подход к решению полиномиальных уравнений, описывающих квантовые схемы», Россия, Дубна, 15 — 19 октября 2007 г.

• 12-ое международное совещание по компьютерной алгебре. Доклад «О роли инволютивных критериев при вычислении булевых базисов Грёбнера», Россия, Дубна, 14 — 15 мая 2008 г.

• Международная конференция «Математическое моделирование и вычислительная физика», ММСР 2009. Доклад «О вычислении булевых инволютивных базисов», Россия, Дубна, 7—11 июля 2009 г.

• Международная конференция «Полиномиальная компьютерная алгебра», РСА 2010. Доклад «Булевы инволютивные базисы и решение задач булевой выполнимости», Россия, Санкт-Петербург, 2 — 7 апреля 2010 г.

• 14-ое международное совещание по компьютерной алгебре. Доклад «Пакет BIBasis для вычисления булевых инволютивных базисов и базисов Грёбнера в системах компьютерной алгебры REDUCE и Масаи1ау2», Россия, Дубна, 2 — 3 июня 2011 г.

Публикации. По материалам диссертации опубликовано 8 печатных работ: 5 статей в рецензируемых журналах, рекомендованных ВАК [28-32], и 3 статьи в сборниках трудов конференций [33-35].

Личный вклад автора. Основные положения и выводы диссертации являются результатом самостоятельных исследований автора, выполненных под руководством д.ф.-м.н., профессора В.П. Гердта. Постановка и формализация задачи, разработка математических моделей и алгоритмов выполнены соискателем совместно с научным руководителем и соавторами. Практическая реализация, исследование форм представления данных, численные расчеты и анализ результатов проводились соискателем самостоятельно. Также соискателем самостоятельно создан и встроен в системы компьютерной алгебры REDUCE и Macaulay2 специализированный пакет для построения булевых базисов Грёбнера, и опубликована работа [32], описывающая данный пакет.

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

Основные результаты диссертационной работы состоят в следующем:

1. Проведено исследование применимости инволютивного алгоритма к задаче построения базисов Грёбнера и базисов Жане в булевом кольце. В результате показано, что инволютивный алгоритм на основе деления Жане, равно как и алгоритм Бухбергера, может быть использован для этой цели только в том случае, когда исходное множество булевых многочленов дополняется множеством всех полевых биномов. После этого вычисление базиса Грёбнера производится в кольце многочленов над полем а искомый булев базис является мультилинейным подмножеством найденного базиса Грёбнера.

2. Разработана версия инволютивного алгоритма на основе деления Пом-маре для построения редуцированных булевых базисов Грёбнера и базисов Поммаре непосредственно в булевом кольце, т.е. без использования полевых мономов. Доказаны корректность и завершаемость данного алгоритма. Показано, что он позволяет эффективно использовать представление булевых многочленов в памяти ЭВМ и простоту их арифметики. Получена точная верхняя оценка на число элементов редуцированного булева базиса Грёбнера.

3. Разработанный булев инволютивный алгоритм на основе деления Поммаре, а также алгоритм на основе деления Жане реализованы на языке программирования С++ в виде отдельных утилит. Дальнейшие изучение и сравнение быстродействия этих утилит между собой и с другими программными пакетами позволили отказаться от некоторых шагов алгоритма и найти компромисс между производительностью и функциональностью. Итоговая версия алгоритма, использующего деление Поммаре, реализована в виде пакета BIBasis, встроенного в системы компьютерной алгебры с открытым исходных кодом Масаи1ау2 и REDUCE. Пакет доступен под лицензией GPL v2.

Благодарности

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

Мне приятно поблагодарить Юрия Анатольевича Блинкова за полезные обсуждения, замечания, критику и помощь в создании пакета BiBasis для системы REDUCE

Я также очень признателен Винфриду Нойну (Winfried Neun) и Дэниэ-лу Грейсону (Daniel Grayson) за согласие и помощь в размещении исходных кодов пакета BiBasis в разрабатываемых ветках систем компьютерной алгебры REDUCE и Macaulay2 соответственно.

И отдельную благодарность я выражаю своей жене — Зининой Александре Александровне, и родителям — Зинину Владимиру Михайловичу и Зининой Татьяне Ивановне за терпение и моральную поддержку, позволившие мне довести данную работу до конца.

Заключение

1. Kandri-Rody A., Weispfenning V. Non-commutative Gröbner bases in algebras of solvable type // Journal of Symbolic Computation. 1990. Vol. 9. Pp. 1-26.

2. Gerdt V. P. On Computation of Gröbner Bases for Linear Difference Systems. // Nuclear Instruments and Methods in Physics Research. 2006. Vol. 559(1). Pp. 211 214. URL: arXiv.org:math-ph/0509050.

3. Brickenstein M. Boolean Gröbner bases — Theory, Algorithms and Applications: Ph. D. thesis / Technischen Universität Kaiserslautern. 2010.

4. Sakai K., Sato Y. Boolean Gröbner Bases, 1988.

5. Марченков С. С. Замкнутые классы булевых функций. Москва: Физматлит, 2000. ISBN: 5-9221-0066-1.

6. Hsiang J., Huang G. Some Fundamental Properties of Boolean Ring Normal Forms // DIMACS series on Discrete Mathematics and Computer Science: The Satisfiability Problem. 1997. Vol. 35. Pp. 587-602.

7. Sato Y., Inoue S., Suzuki A. et al. Boolean Grôbner bases // J. Symb. Comput. 2011. Vol. 46, no. 5. Pp. 622-632.

8. Kalorkoti K. Model checking in the modal /г-calculus and generic solutions // J. Symb. Comput. 2011. Vol. 46, no. 5. Pp. 584-594.

9. Bernasconi A., Codenotti В., Crespi V., Resta G. Computing Grôbner Bases in the Boolean Setting with Applications to Counting.

10. Bardet M., Faugère J.-С., Salvy В., Spaenlehauer P.-J. On the Complexity of Solving Quadratic Boolean Systems. 2011. URL: arXiv.org: 1112. 6263vl.

11. Faugère J.-C. A new efficient algorithm for computing Grôbner bases (F4) // Journal of Pure and Applied Algebra. 1999. Vol. 139, no. 1-3. Pp. 61-88. URL: http://www-salsa.lip6.fr/~jcf/Papers/F99a.pdf.

12. Garey M. R., Johnson D. S. Computers and Intractability: a Guide to the Theory of HV—completeness. New York: Freeman, 1978.

13. Clegg M., Edmonds J., Impagliazzo R. Using the Grobner Basis algorithm to find proofs of unsatisfiability // Proc. 28th Annual ACM Symposium on Theory of Computing. 1996. Pp. 174-183.

14. Dawson C. M., Haselgrove H. L., Hines A. P. et al. Quantum computing and polynomial equations over the finite field // Quantum Information and Computation. 2005. Vol. 5, no. 2. Pp. 102-112. URL: arXiv.org: quant-ph/0408129vl.

15. Mathematica 6.0. Champaign, Illinois, USA: Wolfram Research, Inc., 2007. URL: http://www.wolfram.com/.

16. Arithmetic of Finite Fields. Vol. 5130 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2008.

17. Volny IV F. New Algorithms for Computing Grobner Bases: Ph. D. thesis / Clemson University. 2011. URL: http://etd.lib.clemson.edu/ documents/1306872881/Volnyclemson0050D11180.pdf.

18. Gerdt V. P., Blinkov Y. A. Involutive Bases of Polynomial Ideals // Mathematics and Computers in Simulation. 1998. Vol. 45. Pp. 519-542. URL: arXiv.org:math.AC/9912027.

19. Гердт В. П., Зинин М. В. Инволютивный метод вычисления базисов Грёбнера над F2 // Программирование. 2008. Т. 34, № 4. С. 191-203.

20. Гердт В. П., Зинин М. В. О роли инволютивных критериев при вычислении булевых базисов Грёбнера // Программирование. 2009. Т. 35, № 2. С. 90-97.

21. Gerdt V. P., Zinin М. V. An algorithmic approach to solving polynomial equations associated with quantum circuits // Physics of Particles and Nuclei Letters. 2009. Vol. 6, no. 7. Pp. 521-525.

22. Гердт В. П., Зинин М. В., Блинков Ю. А. О вычислении булевых инво-лютивных базисов // Программирование. 2010. Т. 36, № 2. С. 117-125.

23. Зинин М. В. Пакет BiBasis для вычисления булевых инволютивных базисов и базисов Грёбнера в системах компьютерной алгебры REDUCE и Macaulay2 // Программирование. 2012. Т. 38, № 2. С. 55-67.

24. Gerdt V. Р., Zinin М. V. Gröbner bases over F2 // Computer Algebra and Differential Equations. Vol. 67. 2007. Pp. 59-68.

25. Gerdt V., Zinin M., Blinkov Y. On computation of Boolean involutive bases // Proceedings of International Conference Polynomial Computer Algebra. 2009. Pp. 17-24.

26. Gerdt V. P., Zinin M. V. A Pommaret Division Algorithm for Computing Gröbner Bases in Boolean Rings // Proceedings of ISSAC 2008. ISSAC'08. New York: ACM Press, 2008. Pp. 95-102.

27. Кокс Д., Литтл Д., О'Ши Д. Идеалы, многообразия и алгоритмы. Москва: Мир, 2000. ISBN: 5-03-003320-3.

28. Жарков А. Ю., Блинков Ю. А. Инволютивные системы алгебраических уравнений // Программирование. 1994. Pp. 53-56.

29. Faugere J.-C. FGb. 2012. URL: http://www-polsys.lip6.fr/~jcf/ Software/FGb/index.html.

30. Apel J., Hemmecke R. Detecting Unnecessary Reductions in an Involu-tive Basis Computation: Tech. rep.: RISC, 2002. URL: ftp://ftp.risc. uni-linz.ac.at/pub/techreports/2002/02-22.ps.g.

31. Geddes K. 0., Czapor S. R., Labahn G. Algorithms for Computer Algebra. Kluwer Academic Publishers, 1992.

32. Gerdt V. P., Blinkov Y. A., Yanovich D. A. Computation of Janet Bases. I.Monomial Bases // Computer Algebra in Scientific Computing / CASC 2001. Berlin: Springer-Verlag, 2001. 233-247 pp. URL: http://invo. jinr.ru/Papers/casc01-l.ps.gz.

33. Gerdt V. P., Blinkov Y. A., Yanovich D. A. Computation of Janet Bases. II. Polynomial bases // Computer Algebra in Scientific Computing / CASC 2001. Berlin: Springer-Verlag, 2001. 249-263 pp. URL: http://invo. jinr.ru/Papers/casc01-2.ps.gz.

34. Apel J. A Gröbner Approach to Involutive Bases // Journal of Symbolic Computation. 1995. Vol. 19. Pp. 441-458. URL: http://www.informatik. uni-leipzig.de/~apel/publications/jscl995.ps.

35. Becker T., Weispfenning V., Kredel H. Gröbner bases: A computational approach to commutative algebra. New York: Springer-Verlag, 1993.

36. Engel K. Sperner theory. Cambridge University Press, 1997. 215 pp.

37. Sato Y. Parallel computation of boolean Gröbner bases // ACM SIGSAM Bulletin. 2000. Vol. 34. Pp. 27 28.

38. Gerdt V., Yanovich D. Parallel Computation of Janet and Gröbner bases over rational numbers // Programming and Computer Software. 2005. Vol. 31, no. 2. Pp. 73 80.

39. Zinin M. Utility for computing boolean Groebner and Pommaret bases. 2011. URL: http://bpb.googlecode.com.

40. Grayson D. R., Stillman M. E. Macaulay2, a software system for research in algebraic geometry. 2011. URL: http://www.math.uiuc.edu/ Macaulay2/.

41. Eisenbud D., Grayson D. R., Stillman M. E., Sturmfels B. Computations in algebraic geometry with Macaulay 2. Springer-Verlag, 2001. Vol. 8 of Algorithms and Computations in Mathematics. URL: http://www.math. uiuc.edu/Macaulay2/Book.

42. Исходный код системы компьютерной алгебры Macaulay2. 2011. URL: svn://svn.macaulay2.com/Macaulay2/trunk/M2/.

43. Hearn A. C. REDUCE, a portable general-purpose computer algebra system. 2009. URL: http://www.reduce-algebra.com/.

44. Neun W. Portable Standard Lisp. 1999. URL: http://www2.zib.de/ Symbolik/reduce/.

45. Ltd. C. Codemist Standard LISP. 2002. URL: http://www.codemist. co.uk.

46. Исходный код системы компьютерной алгебры REDUCE. 2011. URL: https://reduce-algebra.svn.sourceforge.net/svnroot/ reduce-algebra/trunk/.

47. Decker W., Greuel G.-M., Pfister G., Schonemann H. Singular 3-1-3 A computer algebra system for polynomial computations. 2011. URL: http: //www.singular.uni-kl.de.

48. Bini D., Mourrain B. Polynomial test suite. 2006. URL: http://www-sop. inria.fr/saga/POL.

49. Verscheide J. The database of polynomial systems. 2011. URL: http: //www.math.ui c.edu/~jan/demo.html.

50. Kornyak V. V. On Compatibility of Discrete Relations // CASC-2005 proceedings. LNCS 3718. Springer-Verlag, 2005. 272-284 pp. URL: arXiv.org:math-ph/0504048.

51. Hoos H. H., Stützle T. SATLIB: An Online Resource for Research on SAT // SAT 2000, Ed. by I. P. Gent, H. V. Maaren, T. Walsh. IOS Press, 2000. 283 292 pp.

52. Brickenstein M., Dreyer A. PolyBoRi: A Gröbner Basis Framework for Boolean Polynomials // Reports of Fraunhofer ITWM. Vol. 122. 2007. URL:http://www.itwm.fraunhofer.de/fileadmin/ITWM-Media/ Zentral/Pdf/BerichteITWM/2007/bericht122.pdf.

53. Hinkelmann F., Arnold E. Fast Gröbner Basis Computation for Boolean Polynomials. 2010. URL: arXiv.org: 1010.2669vl.