КОМПЬЮТЕРНАЯ АЛГЕБРА -
УДК 681.3.06
ПАКЕТ BIBASIS ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ ИНВОЛЮТИВЫХ БАЗИСОВ И БАЗИСОВ ГРЁБНЕРА В СИСТЕМАХ КОМПЬЮТЕРНОЙ АЛГЕБРЫ REDUCE И
MACAULAY2
© 2012 г. М. В. Зинин Лаборатория Информационных Технологий Объединенный Институт Ядерных Исследований 141980 Дубна, Россия mzinin@gmail.com Поступила в редакцию 06.06.2011
В данной работе для двух систем компьютерной алгебры - REDUCE и Macaulay2 - представлен пакет BIBasis, позволяющий вычислять булевы инволютивные базисы и базисы Грёбнера. В соответствующих разделах описаны реализации и пользовательские интерфейсы пакета для каждой из систем. Также приводятся результаты сравнения пакета BIBasis с другими доступными в данных системах компьютерной алгебры пакетами и алгоритмами для построения булевых базисов Грёбнера.
1. ВВЕДЕНИЕ
Инволютивные базисы в кольце многочленов [1] в общем случае являются избыточными базисами Грёбнера и обладают некоторыми полезными свойствами [2] по сравнению с редуцированными базисами Грёб-нера. Широко используемые инволютивные базисы вычисляются с помощью различных вариаций инволютивного алгоритма [3], который также предоставляет эффективный способ построения редуцированного базиса Грёбнера. Искомый редуцированный базис Грёбнера легко получается из известного инволютивного базиса без каких-либо дополнительных редукций, поскольку является его строго определенным подмножеством. Все вышесказанное справедливо не только в общем случае колец коммутативных многочленов, но и в частном случае булевых колец.
Булевы базисы Грёбнера уже доказали свою практическую применимость. Первой впечатляющей демонстрацией возможностей булевых базисов Грёбнера стал "взлом" первого же вызова (challenge) для криптосистемы
HFE (Hidden Fields Equations) с открытым ключом, описанный в [4] и представляющий собой вычисление булева базиса Грёбнера для системы квадратичных булевых многочленов от 80 переменных. С тех пор область применения булевых базисов Грёбнера значительно расширилась, и сейчас есть уже ряд примеров [5] успешного применения этих базисов к решению задач булевой выполнимости SAT (Boolean Satisfiability).
В последние годы разработаны [6, 7, 8], реализованы и использованы для вычисления булевых базисов Грёбнера две версии булева инволютивного алгоритма, основанные на делениях Жане и Поммаре. Практические исследования реализаций этих версий на языке C++ выявили превосходство алгоритма, основанного на делении Поммаре, — в отличие от инволютивного алгоритма в кольце многочленов с рациональными коэффициентами, где деление Жане предпочтительнее, а использование деления Поммаре может привести к построению бесконечного базиса. Результатом этих работ и исследований стал пакет BIBasis (Boolean
Involutive Basis), разработанный для двух открытых систем компьютерной алгебры — REDUCE [9] и Macaulay2 [10]. Пакет реализует инволютивный алгоритм на основе деления Поммаре в булевом кольце многочленов от многих переменных и позволяет вычислять как инволютивные базисы, так и базисы Грёбнера.
В разделе 2 данной работы описаны основные особенности булева кольца, имеющие отношение к вычислению базисов Грёбнера, даны определение деления Поммаре и общий вид инволютивного алгоритма, а также приводятся краткие доводы в пользу применения инволютивного алгоритма и деления Поммаре в булевом кольце и против использования алгоритма Бухбергера. Разделы 3 и 4 посвящены описанию внутреннего устройства пакета BIBasis и его пользовательского интерфейса в каждой из упомянутых систем. В этих же разделах приведены примеры использования пакета. В разделе 5 представлены результаты сравнения BIBasis с другими доступными пакетами и алгоритмами, позволяющими получить булевы базисы Грёбнера. И в заключении делаются выводы о производительности пакета BIBasis и предположения о путях его дальнейшего развития.
2. ИНВОЛЮТИВНЫЙ АЛГОРИТМ НА ОСНОВЕ ДЕЛЕНИЯ ПОММАРЕ В БУЛЕВОМ КОЛЬЦЕ
2.1. Булево кольцо
Булево кольцо есть коммутативное кольцо булевых функций от n переменных, т.е. отображений из {0,1}n на {0,1}. Пусть X := {xi,... ,xn} — множество переменных, F2
— конечное поле, состоящее из двух элементов {0, 1}. Тогда булево кольцо может быть представлено в виде факторкольца
B [X] := F2[X] / <x2 + xi,...,xn + xn > .
Умножение в B [X] идемпотентно, а сложение
— нильпотентно:
V b е B [X] : Ь2 = b, b + b = 0.
Элементы В [X] называются булевыми многочленами и представимы конечными суммами
Е П х
з же п с х
булевых мономов.
Каждый моном представляет собой произведение переменных. Если множество О пусто, то соответствующий моном является единичной булевой функцией 1. Многочлен, состоящий из 0 мономов, является нулевой булевой функцией 0.
Биномы := Ж? + Хг € F2[X] (1 < г < п) называются полевыми многочленами [11, 5], поскольку равенства ^ = 0 определяют ограничения на Хг € F2.
2.2. Деление Поммаре и инволютивный алгоритм
Как и всякое инволютивное деление, деление Поммаре определяется разбиением переменных на мультипликативные и немультипликативные для каждого многочлена / € ^ С F2[X], где множество ^ предполагается конечным. Это разбиение переменных проводится для множества старших мономов и := 1ш(^) и фиксированного допустимого мономиального упорядочения >- [12]. Через Мр (/) обозначим множество мультипликативных по Поммаре переменных многочлена / € ^, через ЖМр(/) := {х1,...,хп}\ Мр(/) — множество немультипликативных переменных.
Произвольное С—разбиение переменных порождает соответствующее деление следующим образом:
Определение 1. [1]. (Старший) моном и € 1ш(^) является С—делителем монома ш, если существует моном V такой, что ш = и ■ V, и V есть либо 1, либо произведение С—мультипликативных переменных и. Обозначается и \с ш.
Общее определение деления Поммаре выглядит так:
Определение 2. [1]. Для (старшего) монома V = ж?1 ••• х?, где йк > 0 (1 < к < п), переменные хк,...,хп являются Р—муль-типликативными.
Для произвольного инволютивного деления L соответствующая L-редукция многочлена p по модулю многочлена f G F определяется аналогично редукции Грёбнера [12]. Единственное отличие состоит в том, что умножение f на соответствующий моном разрешено, только когда моном представляет собой произведение L— мультипликативных переменных f [1].
Обозначим через NFL(p, F) L—нормальную форму p по модулю F и определим инволютив-ный базис идеала I С F2[X]:
Определение 3. [1]. Для данных идеала I, инволютивного деления L и допустимого мономиального упорядочения У, конечное множество G, порождающее I (обозначается I =< G >), называется L—базисом, если
Vg G G , Vx G NM£(g,G) | NF£(g ■ x,G) = 0 .
Подробное описание инволютивного алгоритма приведено в [3]. Здесь же приведем простейшую форму этого алгоритма, который для произвольного деления L и заданных У и конечного F С F2 [X] выдает L—базис идеала I =< F >.
Алгоритм: L—basis (F, У)
Input: F С F2[X], конечное множество; L, инволютивное деление; У, мономиальное упорядочение. Output: G, L-базис < F >.
1: выбрать f G F с наименьшим lm(f)
относительно У 2: G := {f};
3: Q : = F \{f}U{f ■ x | x G NMl(f,F)}; 4: while Q = 0 do 5: h := 0;
6: while Q = 0 и h = 0 do
7: выбрать q G Q с наименьшим lm(q)
относительно У; 8: Q := Q \{q}; 9: h := NF£(q,G); 10: if h = 0 then
11: for all {p G G | lm(h) \L lm(p)} do
12: G := G \{p};
13: Q := Qu{p|\{p-x \ x G NMl(p, G)};
14: G := G U{h};
15: Q := Q u{h ■ x \ x G NM£(h,G)|;
16: return G;
Известно, что результат работы как инволютивного, так и алгоритма Бухбергера зависит от выбранного мономиального упорядочения. И это упорядочение должно быть допустимым [3], т.е.
m = 1 ^^ m У 1 V m, m1 У m2 ^^ mim У m2m V m, mi, m2.
Но, как легко проверить, эти два условия в булевом кольце не совместимы:
xi У x2
*xi
■> x1 *x1 У x1*x2
xi У xi x2
К тому же, хотя B [X] и является кольцом главных идеалов, множество, состоящее из одного булева многочлена {p}, не обязательно является базисом Грёбнера идеала < p >, порожденного этим многочленом. Например:
xi, x2 е < xix2 + xi + x2 >C B [xi, x2].
Поэтому алгоритм Бухбергера неприменим непосредственно в булевом кольце, а чтобы получить с его помощью булев базис Грёбнера, приходится выполнять все вычисления в
кольце F2[X] и использовать полевые биномы
22 22
Jj 1 JJ 1 -J . . . -j Л-'п ^П '
Инволютивный алгоритм, основанный на делении Жане, обладает этими же недостатками в отличие от инволютивного алгоритма на основе деления Поммаре [6]. Последний можно применять непосредственно в булевом кольце, что в свою очередь допускает использование эффективных структур данных для внутреннего представления мономов.
3. ПАКЕТ BIBASIS В СИСТЕМЕ
КОМПЬЮТЕРНОЙ АЛГЕБРЫ REDUCE
Система компьютерной алгебры REDUCE является интерактивной системой общего назначения для математиков, ученых и инженеров. В настоящее время ее возможности в области символьных вычислений включают в себя [9]:
• Все основные символьные алгоритмические операции над многочленами, рациональными функциями и отрезками степенных рядов;
• Автоматическое и управляемое пользователем упрощение выражений;
• Вычисления с символьными матрицами;
• Аналитические дифференцирование и интегрирование;
• Решение достаточно широкого класса алгебраических, трансцендентных и дифференциальных уравнений;
• Вычисления с основными специальными функциями;
• Построения базисов Грёбнера в коммутативной алгебре;
• Оптимизация программ для численных расчетов с символьными входными данными.
REDUCE полностью написана на своем собственном диалекте языка LISP, называемом Standard LISP. Для большинства операционных систем (Unix, Linux, Microsoft Windows, Apple Macintosh) REDUCE доступна в двух версиях, отличающихся реализациями используемого диалекта языка LISP — Portable Standard LISP [13] (PSL) и Codemist Standard LISP [14] (CSL). Отметим, что PSL версия является более быстрой в большинстве случаев, а потому чаще используемой.
С декабря 2008 года REDUCE стала бесплатной системой компьютерной алгебры с открытым исходным кодом, ее разрабатываемая ветка доступна по адресу [15].
REDUCE включает в себя множество разработанных ее
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.