ПРОГРАММИРОВАНИЕ, 2010, No 2, с. 21-30
КОМПЬЮТЕРНАЯ АЛГЕБРА -
УДК 004.92+004.94
ОБОБЩЕНИЕ АЛГОРИТМА F5 ВЫЧИСЛЕНИЯ БАЗИСА ГРЕБНЕРА ПОЛИНОМИАЛЬНЫХ ИДЕАЛОВ
© 2010 г. А. И. Зобнин
Механико-математический факультет МГУ им. М.В. Ломоносова 119992 Москва, Воробьевы горы E-mail: Alexey.Zobnin@gmail.com Поступила в редакцию 01.08.2009 г.
В этой обзорной работе представлен общий подход к известному алгоритму вычисления базисов Гребнера F5, созданному Ж.-Ш. Фожером в 2002 г.
1. ВВЕДЕНИЕ
Алгоритм F5, предназначенный для вычисления базиса Гребнера полиномиального идеала, был предложен Жаном-Шарлем Фожером в 2002 г. [1] и позиционировался как новый алгоритм, исключающий ненужные редукции к нулю в определенных случаях. Особенный интерес к этому алгоритму связан с тем, что с его помощью была решена задача на взлом криптографической системы HFE [2], а также вычислен базис Гребнера системы Cyclic 10 [1]. В исходной версии этого алгоритма требовалось, чтобы образующие идеала были однородными многочленами и образовывали регулярную последовательность. В противном случае алгоритм либо не отсеивал часть нулевых редукций, либо вообще не заканчивал работу. Оригинальное доказательство корректности алгоритма, по общему мнению [3, 4], является сложным и запутанным, а местами содержит неточности и пробелы.
Алгоритм F5 восходит к идеям, представленным Меллером, Морой и Траверсо в 1992 г. [5]. Суть этих идей - использовать базис модуля сизигий для вычисления базиса Гребнера. В алгоритме F5 используются только главные (или тривиальные) сизигии - соотношения вида fj fi — fifj = 0. Для однородных многочленов f1,... ,fn, образующих регулярную последовательность, тривиальные сизигии уже порождают весь модуль сизигий.
В 2003 г. появилась "матричная" версия этого алгоритма, сформулированная в работах [6, 7]
без обоснования, однако более понятная, чем предшествующая "полиномиальная" версия. Последующий цикл работ Ж.-Ш. Фожера и его соавторов был посвящен модификации алгоритма F5/2 для вычисления базиса Гребнера над полем F2 в случае, когда исходная система содержит уравнения поля x2 — Xi = 0. Эти соотношения также использовались в алгоритме, помимо тривиальных сизигий, для отсева нулевых редукций. Для версии F5/2 были получены довольно оптимистичные асимптотические оценки сложности алгоритма [7].
В 2005 г. алгоритм F5 упоминался во втором томе книге Т. Моры "Solving Polynomial Equation Systems" (см. параграф 25.4 работы [8]). Там он рассматривался в духе линейной алгебры при изучении связи базисов Гребнера со ступенчатыми линейными базисами [5, 9]. В том же году появилась дипломная работа Т. Стед-жерса [4], в которой он пытался детально разобраться с "полиномиальной" версией алгоритма. К сожалению, ему не удалолось доказать все необходимые утверждения до конца.
Краткий обзор собственных идей Ж.-Ш. Фо-жер подвел в докторской диссертации 2007 г. [10], в которой, как и в работах [2, 6, 7], представлена без подробного обоснования матричная версия алгоритма. В том же году появилась работа [11], в которой алгоритм F5 использовался для построения базиса сизигий.
В 2008-09 гг. появились циклы препринтов Дж. Перри и К. Эдера [12-14], посвященные
доказательству корректности полиномиальной версии алгоритма для однородных многочленов и более общей формулировке критерия F5.
Наконец, в середине 2009 г. вышла очередная работа Ж.-Ш. Фожера [15], в которой используется обобщение матричной версии алгоритма F5 на случай SAGBI-базисов Гребнера (базисов подалгебр в алгебре многочленов) для решения систем полиномиальных уравнений особого вида.
Известных реализаций алгоритма F5 имеется сравнительно немного:
- закрытая эффективная реализация автора алгоритма - Ж.-Ш. Фожера (2002);
- закрытая эффективная реализация для системы Magma (A. Steel, 2005);
- реализация для системы Maple (R. Pearce, 2005);
- реализация для системы Magma (A. Segers [16], 2004);
- еще одна реализация для системы Magma (T. Stegers [4], 2006);
- реализация для системы Singular (C. Eder, J. Perry, 2009)1;
- реализация для системы Sage (M. Albrecht, J. Perry, 2009)2.
Отметим также экспериментальную реализацию параллельной версии алгоритма F5, работа над которой ведется на механико-математическом факультете МГУ имени М. В. Ломоносова.
В статье предложено упрощенное изложение идеи алгоритма, а также показано, что его можно распространить на случай любых входных наборов многочленов (а не только однородных и образующих регулярную последовательность). Между тем в работе не предлагается какой-либо конкретной эффективной реализации алгоритма, а лишь обсуждаются общие подходы к ее созданию. Мы предполагаем, что читатель знаком с основной работой [1] Ж.-Ш. Фожера. В отличие
xhttp: // www.math.usm.edu/perry/Research/f5_library.
lib.
2 http://bitbucket.org/malb/algebraic_attacks/src/tip/f5.
py.
от работ [4, 12-14], где авторы брали за основу авторскую "полиномиальную" версию алгоритма Р5 и пытались обосновать ее корректность, мы подойдем к алгоритму Е5 с другой стороны, последовательно модифицируя общую схему алгоритма.
В этой статье намеренно используется повествовательный стиль изложения материала, поскольку автор надеется, что такое описание алгоритма Р5 будет более понятным.
2. ИДЕЯ АЛГОРИТМА Е5
Мы будем работать в кольце многочленов К = = Т[хх,..., хп] над некоторым полем Т. Пусть М - множество всех мономов от переменных х1,...,хп. Зафиксируем допустимое упорядочение — на М. Как обычно, через 1т / обозначается старший моном, а через 1с Н - старший коэффициент многочлена Н.
Напомним, что последовательность элементов гх,...,г3 Е К называется регулярной, если гх = = 0 и для всех к, 2 < к < в, г к не является делителем нуля по модулю идеала (гх,..., Гк-\). Другими словами,
дги Е (гх,..., г—) д Е (гх,..., г—).
Регулярность последовательности зависит от порядка элементов, как показывает следующий пример: х, (х — 1)х, (х — 1)у - регулярная последовательность, но (х 1)у, (х — 1)г, х не является регулярной, так как у ■ (х — 1)г Е ((х — 1)у). Однако имеет место следующее утверждение: если многочлены г\,...,г3 однородны по степени, то регулярность такой последовательности не зависит от их порядка.
Пусть требуется вычислить базис Гребнера идеала (/1,..., /т) <К. Припишем каждому многочлену Н, возникающему в ходе вычислений, некоторую сигнатуру 81§(Н) - пару (к,М), где 1 < к < п, а М Е М, такую, что
к
Н = X рг/г,
г=1
где рг Е К - полиномиальные коэффициенты и 1т рк = М (в частности, рк = 0). Здесь к называется индексом, а М - мономом сигнатуры. Конечно, сигнатура многочлена и разложение
по базису определены неоднозначно. Правильнее было бы говорить о сигнатуре данного разложения Н по базису. Но в процессе работы алгоритма каждый обрабатываемый многочлен получается из предыдущих с помощью кольцевых операций, а значит, он естественным образом приобретает некоторое базисное представление и некоторую сигнатуру. Такой многочлен вместе с некоторой приписанной ему сигнатурой мы будем называть отмеченным многочленом. При этом считается, что 81§(/г) = (г, 1). Будем обозначать индекс сигнатуры отмеченного многочлена Н через SigInd Н, а моном сигнатуры - через SigMon Н.
Если задано мономиальное упорядочение —' (не обязательно совпадающее с -—), то оно естественным образом продолжается до порядка на сигнатурах: сначала сравниваются индексы, а затем - мономы. Легко доказать, что он вполне упорядочивает множество сигнатур. Поэтому для всякого многочлена / € I можно ввести понятие минимальной сигнатуры (минимум берется по севозможным разложениям / по базису идеала). Заметим, что, вообще говоря, минимальная и реальная (то есть возникающая в процессе вычислений) сигнатуры могут отличаться.
Итак, пусть Sig(Н) = (к, М). Предположим, что существует д € (/1 , ...,/к-1) < Е, такой, что 1т д | М. Пусть Q - такой моном, что Q 1т д = М. Будем считать для удобства, что 1с д = 1с рк = 1. Это не ограничит общности рассуждений. Тогда запишем рк и Qg в виде рк = М + ¿1, Qg = М + ¿2, где "хвосты" ¿1 и ¿2 младше, чем М. Перепишем выражение для Н через базисные многочлены:
к-1
Н = £ Р/- + (М + ¿1)/к =
г=1 к-1
=£ Рг/г + ^д - ¿2 + ¿1)/к =
г=1 к-1
= £ Рг/г + Шк)д + (¿1 - ¿2)/к.
г=1
Так как д € (/1,..., /к-1), то
h = (Î2 - ti)fk mod (fi,
k-i)-
лучаем, что сигнатура нового представления Н оказалась меньше, чем (к, М).
Мы рассмотрели многочлен д, такой, что SigInd д < к и 1т д | М. В этом случае мы получили, что сигнатуру исходного многочлена Н можно уменьшить. Заметим, что для этого не имеет смысла рассматривать многочлены д, у которых SigInd д = к. В самом деле, если
Q =
M lm g
и д = Я1/1 + ... + Як /к, то условие, поз-
Множитель ¿2 — ¿1 либо равен нулю, либо его старший моном меньше М. В любом случае по-
воляющее переписать Н с меньшей сигнатурой, выглядит так:
1т ^Як/к) = Q • 1т /к • SigMon д — М = Q • 1т д.
В этом случае 1т Як /к — 1т д, то есть 1т д = = 1т (д1/1 + ... Як—1/к—1), а значит, все снова сводится к случаю многочлена из (/1,..., /к—1).
Итак, критерий алгоритма Р5 состоит в том, чтобы отбросить многочлены д € (/1, ...,/к-1) со свойством 1т д | М. Для этого можно последовательно увеличивать текущую сигнатуру и добиваться выполнения такого инварианта: текущий промежуточный базис редуцирует к нулю все многочлены, сигнатура которых меньше текущей. Здесь слово "сигнатура" может пониматься как сигнатура при каком-то представлении (в частности, утверждение будет выполняться и для минимальной сигнатуры). В этом случае, если текущая сигнатура равна (к, М), то многочлен Н из предыдущего рассуждения будет редуцироваться относительно промежуточного базиса к нулю, а значит, его можно не рассматривать.
Идея алгоритма Р5 - поддерживать на каждом шаге этот инвариант и применять критерий. Для этого последовательно вычисляются базисы Гребнера идеалов
(/l), (/1, /2), ... (/1, ... /m),
а при вычислении очередного базиса Гребнера идеала (/1,..., /к) б'-полиномы рассматриваются в порядке возрастания монома сигнатуры. (Для однородных многочленов и степенного упорядочения — это означает, что 5-полин
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.