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

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