ПРОГРАММИРОВАНИЕ, 2008, № 4, с. 8-24
— КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
ИНВОЛЮТИВНЫЙ МЕТОД ВЫЧИСЛЕНИЯ БАЗИСОВ ГРЕБНЕРА НАД Г2*
© 2008 г. В. П. Гердт, М. В. Зинин
Объединенный институт ядерных исследований Лаборатория информационных технологий 141980 г. Дубна Московской обл.
E-mail: gerdt@jirir.ru, mzinin@gmail.com Поступила в редакцию 31.05.2007 г.
В работе рассматривается ииволютивиый алгоритм вычисления базисов Гребнера для полиномиальных идеалов в кольце многочленов от многих переменных над конечным полем F2 и со значениями переменных в F2. Алгоритм использует деление Жане и специализирован для градуированного обратного лексикографического порядка мономов. Мы сравниваем эффективность данного алгоритма и его реализации на С++ с аналогичными показателями алгоритма Бухберге-ра, а также со встроенными алгоритмами вычисления базисов Гребнера в системах компьютерной алгебры Singular, С0С0А и в библиотеке FGb для Maple. В качестве примеров для сравнений взяты адаптированные к F2 некоторые серии примеров, широко используемые для вычисления базисов Гребнера над Q. Полиномиальные системы над F2 и со значениями переменных в F2 представляют интерес, в частности, для моделирования квантовых вычислений и ряда задач криптоанализа.
1. ВВЕДЕНИЕ
В настоящее время стало очевидным, что решение широкого круга прикладных задач требует объединения компьютерных символьных, численных и графических методов. Многие из таких задач сводятся к решению систем алгебраических, дифференциальных или даже конечно-разностных уравнений. Для нелинейных систем, за редчайшим исключением, желаемый ответ может быть получен только численно. Во многих случаях, однако, методы компьютерной алгебры позволяют извлечь из системы уравнений полезную информацию, не вычисляя ее точного решения. Одним из наиболее универсальных способов получения подобной информации является использование базисов Гребнера, ал-
* Исследования, представленные в работе, были выполнены при поддержке гранта РФФИ 07-01-00660 и гранта НШ-5362.2006.2 Президента Российской Федерации для поддержки ведущих научных школ.
горитм построения которых для случая алгебраических систем полиномиального типа был предложен Бухбергером [1, 2] чуть более 40 лет назад. С тех пор базисы Гребнера стали мощным инструментом решения алгебраических полиномиальных уравнений со многими неизвестными, возникающих в различных областях математики и естественных наук. Помимо алгоритма Бухбергера [2], за последнее десятилетие были разработаны другие, более эффективные алгоритмы вычисления базисов Гребнера, такие, как инволютивный алгоритм [3, 4] и алгоритмы и Фожера [5, 6].
Более того, путем прямого обобщения алгоритма Бухбергера и инволютивного алгоритма базисы Гребнера нашли плодотворные применения в некоторых некоммутативных алгебрах [7] и в исследовании линейных дифференциальных и разностных систем уравнений [7-9]. В общем случае систем уравнений с полиномиальной зависимостью от неизвестных (функций) и с алгоритмически "вычислимыми" коэффициентами,
например, рациональными функциями параметров (независимых переменных в случае дифференциальных систем) над полем рациональных чисел с помощью метода базисов Гребнера во многих случаях можно алгоритмически:
1. проверять совместность систем уравнений;
2. находить размерность пространства решений;
3. исключать некоторое подмножество переменных, т.е. получать следствия (если таковые имеются), не содержащие переменных из данного подмножества;
4. "расщеплять" исходную систему на конечное число более простых систем, совокупные решения которых совпадают с решениями исходной системы;
5. преобразовать систему к виду, удобному для численного анализа и решения;
6. исследовать симметрийные и групповые свойства дифференциальных уравнений;
7. выявлять наличие некоторых особых свойств, таких, например, как интегрируемость, в смысле обратной задачи рассеяния, для нелинейных дифференциальных уравнений эволюционного типа для одной пространственной и одной временной переменных.
Важно отметить, что с точки зрения компьютерной алгебры анализ таких различных математических объектов, как дифференциальные либо разностные уравнения в частных производных и полиномиальные алгебраические уравнения, может быть проведен с помощью фактически одного и того же алгоритма. А именно - с помощью алгоритма построения базиса Гребнера для алгебраического полиномиального случая или его аналога для дифференциальных либо разностных уравнений.
Имеется, однако, заметная разница в эффективности современных программных продуктов, вычисляющих алгебраические и дифференциальные (разностные) базисы Гребнера. Богатый опыт, полученный при оптимизации алгоритма построения базисов Гребнера в коммутативной алгебре, пока не перенесен должным образом
на случай дифференциальных и разностных систем уравнений. Кроме того, что алгоритм не завершается в общем нелинейном случае для таких уравнений, основной проблемой остается обнаружение бесполезных нулевых редукций и поиск оптимальных стратегий выбора критических пар (алгоритмы Бухбергера и Фожера) или немультипликативных продолжений (инво-лютивный алгоритм).
В настоящей работе мы рассмотрим специализацию алгоритма Бухбергера и инволютивного алгоритма на случай систем многочленов над простейшим конечным полем F 2 и со значениями переменных в F2. Такие системы многочленов возникают в квантовых вычислениях [10] при построении унитарных матриц для квантовых схем, составленных из вентилей Адама-ра и Тоффоли, образующих универсальный набор квантовых вентилей, а также в ряде актуальных задач криптоанализа для криптосистем с открытым ключом, основанных на трудности установления изоморфизма полиномиальных систем над F 2 [11-13].
2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ
В дальнейшем будем использовать следующие обозначения:
N^o ~~ множество неотрицательных целых чисел.
X = {х\,..., хп} - множество переменных.
R = ЩХ] - кольцо многочленов над полем К характеристики 0.
R' = F2[X] - кольцо многочленов над полем F2.
R = R'/( ~Ь ж 1,..., ж^ + жга) — факторкольцо кольца R' над идеалом (х\ + х\,.. . + +хп). Переменные в составе многочленов этого кольца не имеют степени выше 1, т.е. принадлежат полю F2. Операция умножения мономов в данном кольце определяется следующим образом:
Toi • ТО-2 = Х^ • • • х]■ х^1 ■ ■ ■ X3™ = _ max(n л) ma x(i„,j„)
— X ^ ' ' 'Хп
Определим также понятия наименьшего общего кратного (НОК) и наибольшего общего делителя (НОД) в этом кольце:
lcm (m,i , т2) = lcm (хI1 • • • х\
Ah,к)
max(i„,j„). ' хп 1
gcd(mi, ТП2) = gcd(a;i11
min(iij'i)
= X
min(w„)
Хп
ll
rJl ll
■xi") =
rJn) —
■1 - деление Жане.
М/(и, £7) - множество мультипликативных по Жане переменных для монома и £ II С М. Аналогично для моноида М.
NMJ(u, II) - множество немультипликативных по Жане переменных для монома и £ II С С М. Аналогично для моноида М.
■ьп 1
Id(F) - идеал в R, порожденный F С R. Аналогично для колец R' и R.
М = {х^ • • • | гк £ N^o, 1 ^ к ^ га} - моноид мономов из R. Аналогично для кольца R'.
М = {а^1 •••<» I ik G {0,1}, 1 <: к <: п} -моноид мономов из R.
t = а ■ т, то £ М(М), а £ K(F2) - одночлен.
deg^-w) - степень жг- в мономе и £ М(М).
п
deg(ii) = ^deg^ii) - полная степень и.
%=1
mindeg(f/) = min{ deg(iii),..., deg(-Wfc) } для U = {u1,...,uk}cM(M).
card(F) - число элементов конечного множества F.
idx(i, Т) - индекс элемента t £ Т в упорядоченном множестве Т.
У - допустимое градуированное мономиаль-ное упорядочение, такое, что deg(ii) > > deg(u) => и У v для и, v £ М и х\ У У У ■ ■ ■ У хп. Аналогично для моноида М.
В случае, если моном и делит моном v и deg(ii) < deg(u), т.е. и - собственный делитель v, мы будем писать мс».
lm(/), It(/) и 1с(/) - старшие моном, одночлен и коэффициент / £ i?\{0}, соответственно. Аналогично для колец R' и R.
lm(_F) — множество старших мономов F С R \ {0}. Аналогично для колец R' и R.
NF(f, F) - нормальная форма / £ R по отношению к F С R. Аналогично для колец R' и R.
J (и, U) - подмоноид М, порожденный произведениями степеней переменных из Mj(u, U). Аналогично для моноида М.
и £ U (U С М - конечно) - делитель Жане для v £ М, если v = и ■ w, w £ J(u,U). Аналогично для моноида М.
NFj(f, F) - нормальная форма Жане / £ R по модулю F С R. Аналогично для колец R' и R.
pol(p) = / - первый элемент в тройке р = = {f,g,X}, где f,g £ R. Аналогично для кольца R'.
апс(р = {/, д, X}) = д - второй элемент тройки.
nmp(p = {f,g,X}) = X - подмножество немультипликативных переменных для /.
Следующее определение является стандартным для теории базисов Гребнера [2].
Определение 2.1. Допустимое мономи-альное упорядочение. Линейное мономиальное упорядочение у называется допустимым, если условия
то ф 1 <i=> ту 1, mi У то2 <i=> т\т У то2то выполняются для любых мономов to,toi,to2 £
£ М.
В дальнейшем будем рассматривать только допустимые мономиальные упорядочения, поэтому слово "допустимые" опускаем.
Определение 2.2. Частное в кольце R. Моном т будем называть частным от деления монома b на моном а в кольце R, если т ■ а = Ь и deg(m) = min{deg(m8') | ггц ■ а = b}.
Такой моном всегда один. Докажем это от противного. Пусть имеются мономы т\ ф то2
такие, что а ■ т\ = Ь, а ■ гп2 = Ь и с^(т1) = = deg(m2) = min{deg(mг') | т,- • а = Ь}. Тогда
а ■ gcd(тоl, тг) =
--. . . грО-П . (УрН ( О1^ . . . гуЛп гг.31 . . . -
— ,ьп Ьь<~4 1 ,ьп 1 ,ьп ! — _ тах(сс1,тт(г'и'1)) та.х(а„,тт(г„,у„)) _ ,
— Ж ''' X — О •
Но поскольку т\ ф т2 и deg(тоl)=deg(то2), то очевидно, что т = gcd(ral, гаг) удовлетворяет условиям га ф То1, га ф га2, deg(ra) < < deg(ml) = deg(m2). Таким образом, получаем противоречие с тем, что deg(тоl) = deg(ra2) = = min{deg(mг') | гаг- • а = Ь}.
Заметим, что определенная таким образом операция деления в кольце Я совпадает с операцией деления в кольце Я' в том смысле, что Ь : а = т Ь : а = га, где а,Ь,т £ Я, а
а,Ь,т £ Я' - гомоморфные прообразы а, Ь, га соответственно, совпадающие с ними по виду. Поэтому обозначение отношения делимости -а | Ь - оставим одним и тем же для всех трех упомянутых колец - Я, Я', Я.
Опреде
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.