ПРОГРАММИРОВАНИЕ, 2010, N° 2, с. 72-80
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 004.92+004.94
О ВЫЧИСЛЕНИИ БУЛЕВЫХ ИНВОЛЮТИВНЫХ БАЗИСОВ
*
© 2010 г. В. П. Гердт*, М. В. Зинин*, Ю. А. Блинков*
* Лаборатория информационных технологий Объединенный институт ядерных исследований 141980 Дубна Московской обл. ** Механико-математический факультет Саратовский государственный университет 410071 Саратов, Россия E-mail: gerdt@jinr.ru, mzinin@gmail.com, BlinkovUA@info.sgu.ru Поступила в редакцию 15.08.2009 г.
Базисы Гребнера в булевых кольцах могут быть вычислены с помощью инволютивного алгоритма, основанного на делении Жане или Поммаре. Деление Поммаре позволяет производить вычисления непосредственно в булевом кольце, в то время как деление Жане подразумевает использование кольца многочленов над полем . В данной работе рассматриваются оба деления и сопоставляются дистрибутивное и рекурсивное представление булевых многочленов с точки зрения эффективности вычислений. Приводятся результаты компьютерных экспериментов с обоими представлениями для алгоритма, основанного на делении Поммаре и для лексикографического мономиального упорядочения.
1. ВВЕДЕНИЕ
Несмотря на то, что в булевы базисы Гребнера имеют более чем двадцатилетнюю историю [1], внимание сообщества компьютерной алгебры они стали привлекать лишь 5 лет назад, когда казавшийся "невзламываемым" на современных компьютерах первый криптографический вызов (challenge) для криптосистемы HFE (Hidden Fields Equations) с открытым ключом, описываемый системой квадратичных булевых многочленов от 80 переменных, был успешно "взломан" [2] с помощью вычисления базиса Гребнера по алгоритму F5. Применимость базисов Гребнера к реальным задачам с таким большим числом переменных стала полной неожиданностью для специалистов как в области криптографии, так и в области компьютерной алгебры. В самом деле, в обычных полиномиальных кольцах над Q сложность вычисления бази-
* Исследования, представленные в работе, были выполнены при частичной поддержке гранта 07-01-00660 РФФИ и гранта 1027.2008.2 Министерства Образования и Науки Российской Федерации.
сов Гребнера является экспоненциальной по числу переменных для нульмерных идеалов [3], а для идеалов положительной размерности задача вычисления базисов Гребнера является EX SPACE-полной [4] (см. также недавнюю работу [5], где получена дважды экспоненциальная нижняя оценка на число образующих простого идеала и, тем самым, на число элементов базиса Гребнера).
В случае булевых колец задача выполнимости SAT (Boolean Satisfiability) является .MP-полной (теорема Кука [6, 7]), а построение булева базиса Гребнера решает соответствующую SAT задачу. Ожидаемый экспоненциальный характер оценки сложности построения базиса Гребнера не сработал в случае первого HFE вызова. Причины этого несрабатывания для данной конкретной задачи и алгоритма F5 была выяснена в работе [8].
Первая впечатляющая демонстрация практических возможностей булевых базисов Гребнера послужила толчком к интенсивным исследованиям, ориентированным на различные области применения (см., например, [9-14]), что привело к появлению программного пакета PolyBoRi [10],
вполне сопоставимого по своей эффективности с современными программами, проверяющими булеву выполнимость.
В работах [11] и [12] мы применили инволю-тивные алгоритмы [15, 16], основанные на делениях Жане и Поммаре, для вычисления булевых базисов Гребнера. Результаты испытаний на ряде тестовых примеров показали преимущество реализации для деления Поммаре. Как было установлено в [12], главной предпосылкой этого преимущества является возможность применения деления Поммаре для вычислений непосредственно в булевом кольце, в то время как деление Жане (как и все другие деления) может применяться только для промежуточных вычислений в кольце F2[х?,..., хп], полученном путем добавления полевых биномов х2 +х?,..., х2п+хп к исходному набору булевых многочленов. Таким образом, применение деления Поммаре допускает однобитную векторизацию в представлении мономов, тогда как для реализации деления Жане требуется как минимум 2 бита для хранения степени каждой переменной.
В данной работе мы используем как деление Поммаре, так и деление Жане для решения задачи вычисления булевых базисов Греб-нера. Практический интерес такая задача представляет, например, для моделирования квантовых вычислений на классическом компьютере, а именно для построения унитарных матриц квантовых схем, составленных из вентилей Адамара и Тоффоли [17] - универсального набора квантовых вентилей. Для обоих делений мы рассматриваем новую реализацию алгоритма, основанного на делении Поммаре и использующего адаптированное для лексикографического упорядочивания мономов рекурсивное представление многочленов. Новая реализация сравнивается с предыдущей [12].
2. БУЛЕВЫ ИНВОЛЮТИВНЫЕ БАЗИСЫ
Деления Жане и Поммаре [15, 16] чаще других инволютивных делений упоминаются в литературе (см., например, [18, 19]). В данной работе мы рассматриваем эти деления в применении к кольцу многочленов К := F2[xl,...,xn] над конечным полем F2. Как и всякое инволютивное деление, деления Жане и Поммаре определяются разбиением переменных на мультипликативные и немультипликативные для каждого многочлена / € F С Я, где множество F предпо-
лагается конечным. На самом деле инволютив-ное разбиение переменных проводится для множества старших мономов и := ) и фиксированного допустимого мономиального упорядочения >- [20]. Мы будем использовать наши стандартные (см. [15, 16]) обозначения Мр(/) и MJ(/, F) для множества мультипликативных по Поммаре и Жане переменных многочлена / € F, ЫМТ (/) := {х1, ...,хп}\ Мр (/) и NMJ (/, F) := {xl,...,Xn}\MJ (/, F )-длямно-жества немультипликативных по Поммаре и Жане переменных многочлена / € F. Иногда мы будем писать ^-мультипликативные для мультипликативных по Поммаре переменных и ¿-мультипликативные для мультипликативных по Жане и использовать символ С для обозначения любого из этих двух делений (разбиений переменных).
Здесь и далее степень монома и по переменной х,, будем обозначать как degi(u), а полную степень и - как deg(u). С-разбиение переменных порождает соответствующее деление следующим образом.
Определение 1 [15]. (Старший) моном и € € ) является С-делителем монома w, если существует моном V такой, что w = и ■ V, и V есть либо 1, либо произведение С-мультиплика-тивных переменных и.
Теперь определим разделения переменных, порождающие деления Поммаре и Жане [15].
Определение 2 [15]. Для (старшего) монома V = х?1 ■ ■ ■хк", где dk > 0 (1 < к < п), переменные хк,.. .,хп являются V-мультипликативны-ми.
Определение 3 [15]. Пусть и С ) - конечное множество. Для каждого 0 < г < п разобьем и на группы и обозначим их неотрицательными целыми do, ...,с!^
^о, dl,..., di] :=
:= {и € и | d0 = 0^1 = deg1(u), ■ ■ ■ = degi(u)}.
Для и € ..., di-1] переменная х1 является ГТ-мультипликативной, если
degi(и) = max{degi(v) | V € ..., di-1]} .
Для данного инволютивного деления С (С = V или С = ГГ) соответствующая С-редукция многочлена р по модулю многочлена / € F определяется аналогично редукции Гребнера [20]. Единственное отличие состоит в том, что умножение
Input: F С B, конечное множество; L, инволютивное деление; У,
мономиальное упорядочение
Output: G, L-базис < F >
1 выбрать f E F с наименьшим lm(f) относительно У
2 G := {f}; Q := F \{f }U{f ■ x | x E NMf F)}
3 do
4 h := 0
5 while Q = 0 и h = 0 do
6 выбрать q E Q с наименьшим lm(q) относительно У
7 Q := Q \{q}; h := NFC(q,G)
8 : od
9 if h = 0 then
10 for all {p E G 1 lm(h) Il lm(p)} do
11 G := G \{p};
12 Q := Q U{p}\{p ■ x I x E NMl(p, G)}
13 od
14 G := G U {h}; Q := Q U{h ■ x | x E NMc(h, G)}
15 fi
16 od while Q = 0
17 return G
Рис. 1. Алгоритм L-basis(F, у).
/ на соответствующий моном разрешено, только когда моном представляет собой произведение С-мультипликативных переменных / [15].
Будем обозначать С-нормальную форму р по модулю ¥ через М¥с(р,¥). Тогда инволютив-ный базис идеала I С К определяется следующим образом.
Определение 4 [15]. Для данных идеала I, инволютивного деления С и допустимого моно-миального упорядочения У конечное множество С, порождающее I (обозначается I = < С >), называется С-базисом, если
Vд е С,Ух е МИс(д,С) | МГс(д ■ х, С) = 0 . (1)
Теорема 1 [15]. Инволютивный базис является (в общем случае избыточным) базисом Гребнера.
В качестве булева кольца В, как кольца булевых функций от п переменных, можно рассматривать фактор-кольцо вида [10]
В := К/ <х1 + х\,...,х2п + х > . (2)
Умножение в В идемпотентно, сложение -нильпотентно:
V Ь е В | Ь2 = Ь, Ь + Ь = 0 .
Элементы В являются (полилинейными) булевыми многочленами и могут быть представлены в виде конечных сумм
Е П х
] хе Qjс{х1,...,х„}
булевых мономов. К отображается в В с помощью канонического гомоморфизма колец, определенного в правой части (2):
ф : К ^ В . (3)
Алгоритм, приведенный на рис. 1, для С = V выдает [12] V-базис идеала I =< ¥ > для заданных У и конечного ¥ С В. В случае деления Жане (С = Г) и конечного набора ¥ С К полилинейных многочленов этот же алгоритм может быть применен для вычисления булевого Г-базиса идеала ф(< ¥ >) С В, если конечный набор ¥ дополнить множеством полевых биномов
Ф := {х( + х 1,..., хп + хп},
и вычисление базиса проводить в К. Тогда образ результата, полученный по формуле (3), т.е. подмножество полилинейных многочленов этого результата, является Г-базисом в В [11, 12].
Поскольку этот алгоритм строит минимальный L-базис [15, 16], он выдает один и тот же булев базис для обоих делений. Это непосредственно вытекает из следующего факта.
Утверждение 1 [21]. Если идеал в R имеет конечный базис Поммаре, то он совпадает с минимальным базисом Жане G этого же идеала, и Уд е G | NMP (g) = NMj (д, G).
В самом деле, благодаря наличию полевых биномов P-базис всегда конечен для любого исходного набора полилинейных (булевых) многочленов в R.
Однако, поведение алгоритма может отличаться для P - и J -делений. После выполнения цикла for на строках 10-13 алгоритма множество G на каждой итерации является L-авто
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.