"Записки научных семинаров ПОМИ"

Том 543, стр. 191-221

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

alch@pdmi.ras.ru

Аннотация: При помощи замены переменных мы сводим проблему построения корней многочлена в поле кратных формальных дробно--степенных рядов в нулевой характеристике к построению корней другого многочлена в кольце формальных степенных рядов. Получены эффективные оценки для данной замены переменных. Для достижения этой цели, предлагается более тонкая версия результата о сложности алгоритма Ньютона-Пюизе. После этого можно применить алгоритм с эффективным временем работы для факторизации полиномов над кольцами формальных степенных рядов, построенный автором ранее. Библ. -- 8 назв.
Ключевые слова: формальные дробно-степенные ряды, формальные степенные ряды, факторизация многочленов, многие переменные, сложность алгоритмов [formal fractional power series, formal power series, factoring polynomials, many variables, complexity of the algorithms]