Preview

Труды Института системного программирования РАН

Расширенный поиск

Минимальный базис модуля сизигий старших членов

https://doi.org/10.15514/ISPRAS-2018-30(6)-16

Полный текст:

Аннотация

Системы полиномиальных уравнений - один из наиболее универсальных математических объектов. Почти все задачи криптографического анализа можно свести к поиску решений систем полиномиальных уравнений. Соответствующее направление исследований принято называть алгебраическим криптоанализом. С точки зрения вычислительной сложности, системы полиномиальных уравнений охватывают весь диапазон возможных вариантов, от алгоритмической неразрешимости диофантовых уравнений до хорошо известных эффективных методов решения линейных систем. Метод Бухбергера приводит систему алгебраических уравнений к системе специального вида, определяемой базисом Гребнера исходной системы уравнений, позволяющему использовать исключение зависимых переменных. Фундаментом определения базиса Гребнера является допустимое упорядочение на множестве термов. Множество допустимых упорядочений на множестве термов бесконечно и даже континуально. Наиболее трудоемким этапом при нахождении базиса Гребнера с помощью алгоритма Бухбергера является доказательство приводимости к нулю всех S-многочленов. Известно, что достаточно провести такую проверку только для любого подмножества таких многочленов, представляющих систему образующих K[X]-модуля S-многочленов. Возникает естественная задача нахождения такой минимальной системы образующих. Существование такой системы образующих следует из теоремы Накаямы. Предложен алгоритм построения такого базиса для любого упорядочения.

Об авторе

А. В. Шокуров
Институт системного программирования им. В.П. Иванникова РАН
Россия


Список литературы

1. . Gebauer R., Moller H.M. On an Instalation of Buchberger’s Algorithm. Journal of Symbolic Computation, no. 6, 1987, pp. 257-286..

2. . Caboara M., Kreuzer M., Robbiano L. Efficiently computing minimal sets of critical pairs, Journal of Symbolic Computation, No. 38, 2004, pp. 1169-1190.

3. . Ленг С.. Алгебра. Москва, Мир, 1968.

4. . Агиевич С.В. Усовершенствованый алгоритм Бухбергера. Труды Института математики НАН Беларуси, том 20, no. 1, 2012, стр. 3-13.

5. . Buchberger B. Grobner Bases: An Algorithmic Method in Polynomial Ideal. In Multidimensional Systems Theory and Applications, 1985, pp. 184-232.


Для цитирования:


Шокуров А.В. Минимальный базис модуля сизигий старших членов. Труды Института системного программирования РАН. 2018;30(6):293-304. https://doi.org/10.15514/ISPRAS-2018-30(6)-16

For citation:


Sokurov A.V. Minimal basis of the syzygies module of leading terms. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(6):293-304. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(6)-16

Просмотров: 93


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)