ПРОГРАММИРОВАНИЕ, 2009, № 2, с. 43-52
— КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
О РОЛИ ИНВОЛЮТИВНЫХ КРИТЕРИЕВ ПРИ ВЫЧИСЛЕНИИ БУЛЕВЫХ БАЗИСОВ ГРЕБНЕРА*
© 2009 г. В. П. Гердт, М. В. Зинин
Объединенный институт ядерных исследований Лаборатория информационных технологий 141980 г. Дубна Московской обл. E-mail: gerdt@jirir.ru, mzinin@gmail.com Поступила в редакцию 01.06.2008 г.
В данной работе изучается эффективность применения четырех критериев в инволютивном алгоритме, основанном на делении Поммаре, при его применении для построения булевых базисов Гребнера. Одним из результатов проведенного исследования является тот факт, что при вычислениях в булевых кольцах критерии играют заметно меньшую роль, чем при вычислениях в обычном кольце многочленов над полем целых чисел. Другим результатом исследования является более высокая эффективность второго и/или третьего критерия по сравнению с двумя остальными.
1. ВВЕДЕНИЕ
Как алгоритмический инструмент базисы Гребнера проявили свою практическую применимость для решения многих важных задач, в том числе и для особых случаев, таких, как булевы многочлены, т.е. многочлены, в которых коэффициенты и показатели степеней переменных принимают значения либо 0, либо 1. Среди наиболее впечатляющих приложений отметим первую сложную проблему HFE (Hidden Fields Equations) в криптографии с открытым ключом. Впервые [1] эта задача была решена с помощью алгоритма [2], позднее [3] - с помощью алгоритма F4 [4].
Еще одним многообещающим применением булевых базисов Гребнера может стать моделирование квантовых вычислений на классическом компьютере. На практике, в настоящее время удается промоделировать лишь 20-25 q-битные схемы из-за ограниченности памяти компьютера. Экспоненциальная сложность по-
* Исследования, представленные в работе, были выполнены при поддержке гранта РФФИ 07-01-00660 и гранта НШ-5362.2006.2 Президента Российской Федерации для поддержки ведущих научных школ.
строения базисов Гребнера в булевых кольцах [5] и возможность вычислять булевые базисы Гребнера для систем многочленов от 80 [1, 3] и даже более чем от 100 переменных [6] дают реальную надежду на то, что базисы Гребнера, по крайней мере в отдельных случаях, позволят сильно продвинуться в моделировании квантовых вычислений.
В данной работе представлено исследование роли инволютивных критериев для алгоритма, впервые описанного в [7], затем улучшенного в [8, 9] и специализированного для булевых колец [10]. Алгоритм использует инволютивное деление, названное делением Поммаре [7], и, в силу специфики данного деления, не использует дополнительные полевые многочлены. Это дает возможность [10], помимо прочего, уменьшить число промежуточных продолжений и редукций и использовать максимально возможную векторизацию в представлении мономов.
Более подробное описание представленного ниже алгоритма PoшшaгeШasis можно найти в [10], там же приводится доказательство корректности и завершаемости алгоритма, в том числе и для случая булева кольца. Однако, в [10] представлены результаты тестирования
простейшей версии алгоритма РогшпагеШав!^, в которой, в частности, не были реализованы ин-волютивные критерии. Изучение путем компьютерных экспериментов эффекта от применения четырех инволютивных критериев, цель которых - предотвратить бесполезные редукции, и есть цель настоящей работы. В соответствующем разделе будут представлены графики, иллюстрирующие влияние, которое оказывают различные сочетания критериев на время работы алгоритма на разных примерах.
2. ДЕЛЕНИЕ ПОММАРЕ В БУЛЕВОМ КОЛЬЦЕ
2.1. Булево кольцо
Пусть х := {х\,..., хп} - множество переменных, 1^2 [х] - коммутативное кольцо многочленов над конечным полем F2 из двух элементов {0,1}, и 1 С [х] - идеал. Если набор многочленов Р = {р\,... ,рк} является базисом X, мы будем записывать этот факт как 1 =< Р >.
Булево кольцо - это кольцо булевых функций от п переменных, т.е. отображения из {0,1 }п на {0,1}. Это кольцо коммутативно и может быть представлено как факторкольцо
[х] := Г2[х]/ < х1 + х 1
,..., |
+ хп >
Умножение в В[х] идемпотентно, а сложение -нильпотентно:
V Ъ е В[х] : Ъ2 = Ь, Ь + Ь = 0.
Элементы В[х] называются булевыми многочленами и представимы конечными суммами
£ П -
] сх
(1)
булевых мономов.
Каждый моном представляет собой произведение переменных. Если множество пусто, то соответствующий моном является единичной булевой функцией 1. Многочлены из ^[х] вида (1) также будем называть булевыми. Биномы уз,- := х\ + Х{ 6 [х] (1 < I < п) называются полевыми многочленами [5, 6], поскольку равенства = 0 определяют ограничения на Х{ 6
2.2. Деление Поммаре
Пусть >- - допустимое мономиальное упорядочивание, такое, что
х1 У х2■ ■ ■ У хп.
Следующие определения [7] и обозначения относятся к обоим кольцам ^[х] и В[х]. Будем обозначать старший моном многочлена р через 1т(р). Соответственно, для множества Р многочленов их старшие мономы образуют множество 1т (Р). Степень переменной жг- в составе монома т будем обозначать через с^Дга).
Определение 1. Для многочлена р такого, что
1ш(р) = жI1 ■ ■ ■ х^1 х1к, 1 < к < п, (1к > 0,
переменные из множества ИМ-р{р) := {х\,..., Хк-г} называются Поммаре- или V-немультипликативными, а остальные переменные из множества х - V-мультипликативными. Для р = 1 все переменные считаются (Р-) мультипликативными. Моном V называется делителем Поммаре или Р-делителем монома и (обозначение: V |-р и). Соответственно, и называется Р-кратным V, если и = V ■ т и все переменные, присутствующие в т в ненулевой степени, являются ^-мультипликативными для V.
Деление Поммаре является инволютивным [7] и удовлетворяет условию
Vи, : и \-р т А V \-р т => и \-р V V V \-р и.
Для двух заданных многочленов р, д 6 [х] (или р,д £ В[х]), таких, что р содержит моном и, удовлетворяющий условию 1т (д) \-р и, многочлен р называется Р-приводимым по модулю д и допускает элементарное Р-приведение
Р Р + ЗТ—гт-9 1т (г)
(2)
В противном случае р называется Р-неприво-димым по модулю д. Если Б - набор многочленов и многочлен р Р-неприводим по модулю любого / 6 Б, то говорят, что р находится в Р-нормальной форме по модулю Б (обозначение: р = ИБ-р(р, Б)). Приведение (2) будем называть булевым, если оба многочлена р и д - булевы.
1 choose / £ F с наименьшим lm(pol(/)) относительно у
2 т := {/, Л; Q := {{q, q} | q £ F \ {/}} U {{/ •ж,/} ж £ NMv(f)}
3 do
4 h := 0
5 while Q / 0 и /г = 0 do
6 choose q £ Q с наименьшим lm(pol(g)) относительно у
7 Q-=Q\{q}-,
8 h := HeadNF-p (q, P)
9 od
10 if h ф 0 then
11 for all {p £ P \ lm(pol(/i)) \-p lm(pol(p))} do
12 P:=P\{p};
13 Q:=QU{p}\ {{pol(p) • x, pol(p)} | ж £ NMv{p)}
14 od
15 P := P U {h, h}; Q := Q U {{h ■ ж, h} | ж £ NMv(h)}
16 fi
17 od while Q ф 0
18 T := AutoreducePails-p(P)
19 return P
Рис. 1. Алгоритм PommaretBasis(F, -<).
Набор многочленов Р называется Р-авто-редуцированным, если
У/е*1 : / = {/}) . (3)
Из условия (3) следует, что в случае, когда набор многочленов Р Р-авторедуцирован, моном и может иметь не более одного Р-делителя в Это означает единственность нормальной формы NР-р(р, Р) для любого многочлена
Р [9].
Р-авторедуцированный набор Р называется базисом Поммаре идеала < Р >, если
уР е р,Ух е нмТ{р) ■. мрт(р-х,р) = о. (4)
Произведение р ■ х в (4) называется (V-) немультипликативным продолжением р по переменной х.
3. ИНВОЛЮТИВНЫЙ АЛГОРИТМ НА ОСНОВЕ ДЕЛЕНИЯ ПОММАРЕ С ИСПОЛЬЗОВАНИЕМ КРИТЕРИЕВ
3.1. Алгоритм РоттагеЬВаБ'т
Пусть В \ {0} - конечный набор булевых мно-
п
гочленов вида (1), и Ф := + жг}.
г = 1
Приведенный на рис. 1 алгоритм PommaretBasis [10] вычисляет базис Поммаре идеала < F > в кольце -F2M Для F := В иФ либо прямо в кольце В[х]. В первом случае булев базис Поммаре является подмножеством результирующего базиса, состоящим из булевых многочленов. На практике более эффективно производить вычисления прямо в булевом кольце [10], что и будет предполагаться в дальнейшем.
Данный алгоритм представляет собой простейшую версию более общего инволютивного алгоритма InvolutiveBasis [8, 9], специализированного для деления Поммаре.
Корректность и завершаемость данного алгоритма без использования критериев доказаны в [10]. Учет критериев, корректность которых доказана в [7, 11], очевидно, не нарушает этих свойств алгоритма.
Подалгоритм HeadNF-p (р, Р) вычисляет головную нормальную форму по Поммаре многочлена в р относительно многочленов, входящих во множество Р. При этом р состоит из пары многочлен-предок, в которой многочлен обозначается как pol(p), а его предок -как апс(р). Предком многочлена называется
1 h:= pol(p); G := {po\(g) \ g £ T}
2 if lm(/i) Поммаре-неприводим по модулю G then
3 return h
4 else
5 выбрать g £ T такой, что lm(pol(g)) \p lm(/i)
6 if lm(/i) ф lm(anc(/i)) и Criteria(p, g) then
7 return 0
8 else
9 while h ф 0 и lm(/i) Поммаре-приводим по модулю G do
10 выбрать q £ T такой, что lm(g) \p lm(/i)
11 h:=h - q- lt(h)/ lt(g)
12 od
13 fi
14 fi
15 return h
Рис. 2. Алгоритм HeadNF-p(p, Т).
многочлен промежуточного базиса G в алгоритме PommaretBasis с минимальным по полной степени старшим мономом, немультипликативными продолжениями которого многочлен pol(p) был получен в процессе работы алгоритма. При этом все (промежуточные) многочлены таких продолжений должны иметь неприводимые (по Поммаре) старшие мономы. Если заданный многочлен промежуточного базиса не имеет предка в этом базисе, то такой многочлен рассматривается как предок самого себя (см. более формальное определение предка в [9]).
Множество Т - второй аргумент подалгорит-ма HeadNFp - содержит пары многочлен-предок для промежуточного базиса G.
Полный набор из четырех инволютивных критериев эквивалентен, в совокупности [11], критериям Бухбергера [12]. Этот набор включает два критерия, описанных в [7], и еще два, описание которых можно найти в [11]. Если результат хотя бы одного критерия - истина, то многочлен в р будет, в итоге, (не обязательно на данном этапе работы алгоритма) редуцирован к 0. Поэтому его редукцию (вычисление нормальной формы) можно исключить, что и делается в подалгоритме HeadNF-p на ша
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.