Алгоритмы полиномиальной сложности для вычислительных задач теории алгебраических кривых

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