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

Системы полиномиальных уравнений - один из наиболее универсальных математических объектов. Почти все задачи криптографического анализа можно свести к поиску решений систем полиномиальных уравнений. Соответствующее направление исследований принято называть алгебраическим криптоанализом. С точки зрения вычислительной сложности, системы полиномиальных уравнений охватывают весь диапазон возможных вариантов, от алгоритмической неразрешимости диофантовых уравнений до хорошо известных эффективных методов решения линейных систем. Метод Бухбергера приводит систему алгебраических уравнений к системе специального вида, определяемой базисом Гребнера исходной системы уравнений, позволяющему использовать исключение зависимых переменных. Фундаментом определения базиса Гребнера является допустимое упорядочение на множестве термов. Множество допустимых упорядочений на множестве термов бесконечно и даже континуально. Наиболее трудоемким этапом при нахождении базиса Гребнера с помощью алгоритма Бухбергера является доказательство приводимости к нулю всех 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.