Сложность построения корней многочлена в поле кратных формальных дробно-степенных рядов в нулевой характеристике

А. Л. Чистов

Санкт-Петербургское отделение Математического института им. В. А. Стеклова Российской академии наук, наб. р. Фонтанки 27, 191023 Санкт-Петербург, Россия

Аннотация: При помощи замены переменных мы сводим проблему построения корней многочлена в поле кратных формальных дробно–степенных рядов в нулевой характеристике к построению корней другого многочлена в кольце формальных степенных рядов. Получены эффективные оценки для данной замены переменных. Для достижения этой цели, предлагается более тонкая версия результата о сложности алгоритма Ньютона-Пюизе. После этого можно применить алгоритм с эффективным временем работы для факторизации полиномов над кольцами формальных степенных рядов, построенный автором ранее. Библ. – 8 назв.

Ключевые слова: формальные дробно-степенные ряды, формальные степенные ряды, факторизация многочленов, многие переменные, сложность алгоритмов.

УДК: 513.6, 518.5